C#, Evil code, Noda Time

Type initializer circular dependencies

28 Comments

To some readers, the title of this post may induce nightmarish recollections of late-night debugging sessions. To others it may be simply the epitome of jargon. Just to break the jargon down a bit:

  • Type initializer: the code executed to initialize the static variables of a class, and the static constructor
  • Circular dependency: two bits of code which depend on each other – in this case, two classes whose type initializers each require that the other class is initialized

A quick example of the kind of problem I’m talking about would be helpful here. What would you expect this code to print?

using System;

class Test
{    
    static void Main()
    {
        Console.WriteLine(First.Beta);
    }
}

class First
{
    public static readonly int Alpha = 5;
    public static readonly int Beta = Second.Gamma;
}

class Second
{
    public static readonly int Gamma = First.Alpha;
}

Of course, without even glancing at the specification, any expectations are pretty irrelevant. Here’s what the spec (section 10.5.5.1 of the C# 4 version):

The static field variable initializers of a class correspond to a sequence of assignments that are executed in the textual order in which they appear in the class declaration. If a static constructor (§10.12) exists in the class, execution of the static field initializers occurs immediately prior to executing that static constructor. Otherwise, the static field initializers are executed at an implementation-dependent time prior to the first use of a static field of that class.

In addition to the language specification, the CLI specification gives more details about type initialization in the face of circular dependencies and multiple threads. I won’t post the details here, but the gist of it is:

  • Type initialization acts like a lock, to prevent more than one thread from initializing a type
  • If the CLI notices that type A needs to be initialized in order to make progress, but it’s already in the process of initializing type A in the same thread, it continues as if the type were already initialized.

So here’s what you might expect to happen:

  1. Initialize Test: no further action required
  2. Start running Main
  3. Start initializing First (as we need First.Beta)
  4. Set First.Alpha to 5
  5. Start initializing Second (as we need Second.Gamma)
  6. Set Second.Gamma to First.Alpha (5)
  7. End initializing Second
  8. Set First.Beta to Second.Gamma (5)
  9. End initializing First
  10. Print 5

Here’s what actually happens – on my box, running .NET 4.5 beta. (I know that type initialization changed for .NET 4, for example. I don’t know of any changes for .NET 4.5, but I’m not going to claim it’s impossible.)

  1. Initialize Test: no further action required
  2. Start running Main
  3. Start initializing First (as we need First.Beta)
  4. Start initializing Second (we will need Second.Gamma)
  5. Set Second.Gamma to First.Alpha (0)
  6. End initializing Second
  7. Set First.Alpha to 5
  8. Set First.Beta to Second.Gamma (0)
  9. End initializing First
  10. Print 0

Step 5 is the interesting one here. We know that we need First to be initialized, in order to get First.Alpha, but this thread is already initializing First (we started in step 3) so we just access First.Alpha and hope that it’s got the right value. As it happens, that variable initializer hasn’t been executed yet. Oops.

(One subtlety here is that I could have declared all these variables as constants instead using "const" which would have avoided all these problems.)

Back in the real world…

Hopefully that example makes it clear why circular dependencies in type initializers are nasty. They’re hard to spot, hard to debug, and hard to test. Pretty much your classic Heisenbug, really. It’s important to note that if the program above had happened to initialize Second first (to access a different variable, for example) we could have ended up with a different result. In particular, it’s easy to get into a situation where running all your unit tests can cause a failure – but if you run just the failing test, it passes.

One way of avoiding all of this is never to use any type initializers for anything, of course. In many cases that’s exactly the right solution – but often there are natural uses, particularly for well-known values such as Encoding.Utf8, TimeZoneInfo.Utc and the like. Note that in both of those cases they are static properties, but I would expect them to be backed by static fields. I’m somewhat ambivalent between using public static readonly fields and public static get-only properties – but as we’ll see later, there’s a definite advantage to using properties.

Noda Time has quite a few values like this – partly because so many of its types are immutable. It makes sense to create a single UTC time zone, a single ISO calendar system, a single "pattern" (text formatter/parser) for each of a variety of common cases. In addition to the publicly visible values, there are various static variables used internally, mostly for caching purposes. All of this definitely adds complexity – and makes it harder to test – but the performance benefits can be significant.

Unfortunately, a lot of these values end up with fairly natural circular dependencies – as I discovered just recently, where adding a new static field caused all kinds of breakage. I was able to fix the immediate cause, but it left me concerned about the integrity of the code. I’d fixed the one failure I knew about – but what about any others?

Testing type initialization

One of the biggest issues with type initialization is the order-sensitivity – combined with the way that once a type has been initialized once, that’s it for that AppDomain. As I showed earlier, it’s possible that initializing types in one particular order causes a problem, but a different order won’t.

I’ve decided that for Noda Time at least, I want to be reasonably sure that type initialization circularity isn’t going to bite me. So I want to validate that no type initializers form cycles, whatever order the types are initialized in. Logically if we can detect a cycle starting with one type, we ought to be able to detect it starting with any of the other types in that cycle – but I’m sufficiently concerned about weird corner cases that I’d rather just take a brute force approach.

So, as a rough plan:

  • Start with an empty set of dependencies
  • For each type in the target assembly:
    • Create a new AppDomain
    • Load the target assembly into it
    • Force the type to be initialized
    • Take a stack trace at the start of each type initializer and record any dependencies
  • Look for cycles in the complete set of dependencies

Note that we’ll never spot a cycle within any single AppDomain, due to the way that type initialization works. We have to put together the results for multiple initialization sequences to try to find a cycle.

A description of the code would probably be harder to follow than the code itself, but the code is relatively long – I’ve included it at the end of this post to avoid intefering with the narrative flow. For more up-to-date versions in the future, look at the Noda Time repository.

This isn’t a terribly nice solution, for various reasons:

  • Creating a new AppDomain and loading assemblies into it from a unit test runner isn’t as simple as it might be. My code doesn’t currently work with NCrunch; I don’t know how it finds its assemblies yet. When I’ve fixed that, I’m sure other test runners would still be broken. Likewise I’ve had to explicitly filter types to get TeamCity (the continuous integration system Noda Time uses) to work properly. Currently, you’d need to edit the test code to change the filters. (It’s possible that there are better ways of filtering, of course.)
  • It relies on each type within the production code which has an "interesting" type initializer to have a line like this:
    private static readonly int TypeInitializationChecking = NodaTime.Utility.TypeInitializationChecker.RecordInitializationStart();
  • Not only does the previous line need to be added to the production code – it clearly gets executed each time, and takes up heap space per type. It’s only 4 bytes for each type involved, and it does no real work when we’re not testing, but it’s a nuisance anyway. I could use preprocessor directives to remove the code from non-debug or non-test-targeted builds, but that would look even messier.
  • It only picks up cycles which occur when running the version of .NET the tests happen to execute on. Given that there are ordering changes for different versions, I wouldn’t like to claim this is 100% bullet-proof. Likewise if there are only cycles when you’re running in some specific cultures (or other environmental features), it won’t necessarily pick those up.
  • I’ve deliberately not tried to make the testing code thread-safe. That’s fine in Noda Time – I don’t have any asynchronous operations or new threads in Noda Time at all – but other code may need to make this more robust.

So with all these caveats, is it still worth it? Absolutely: it’s already found bugs which have now been fixed.

In fact, the test didn’t get as far as reporting cycles to start with – it turned out that if you initialized one particular type first, the type initializer would fail with a NullReferenceException. Ouch! Once I’d fixed that, there were still quite a few problems to fix. Somewhat coincidentally, fixing them improved the design too – although the user-visible API didn’t change at all.

Fixing type initializer cycles

In the past, I’ve occasionally "fixed" type initialization ordering problems by simply moving fields around. The cycles still existed, but I figured out how to make them harmless. I can say now that this approach does not scale, and is more effort than it’s worth. The code ends up being brittle, hard to think about, and once you’ve got more than a couple of types involved it’s really error-prone, at least for my brain. It’s much better to break the cycle completely. To this end, I’ve ended up using a fairly simple technique to defer initialization of static variables. It’s a poor-man’s Lazy<T>, to some extent – but I’d rather not have to write Lazy<T> myself, and we’re currently targeting .NET 3.5…

Basically, instead of exposing a public static readonly field which creates the cycle, you expose a public static readonly property – which returns an internal static readonly field in a nested, private static class. We still get the nice thread-safe once-only initialization of a type initializer, but the nested type won’t be initialized until it needs to be. (In theory it could be initialized earlier, but a static constructor would ensure it isn’t.) So long as nothing within the rest of the type initializer for the containing class uses that property, we avoid the cycle.

So instead of this:

// Requires Bar to be initialized – if Bar also requires Foo to be
// initialized, we have a problem…
public static readonly Foo SimpleFoo = new Foo(Bar.Zero);

We might have:

public static readonly Foo SimpleFoo { get { return Constants.SimpleFoo; } }

private static class Constants
{
    private static readonly int TypeInitializationChecking = NodaTime.Utility.TypeInitializationChecker.RecordInitializationStart(); 

    // This requires both Foo and Bar to be initialized, but that’s okay
    // so long as neither of them require Foo.Constants to be initialized.
    // (The unit test would spot that.)
    internal static readonly Foo SimpleFoo = new Foo(Bar.Zero);
}

I’m currently undecided about whether to include static constructors in these classes to ensure lazy initialization. If the type initializer for Foo triggered the initializer of Foo.Constants, we’d be back to square one… but adding static constructors into each of these nested classes sounds like a bit of a pain. The nested classes should call into the type initialization checking as well, to validate they don’t cause any problems themselves.

Conclusion

I have to say, part of me really doesn’t like either the testing code or the workaround. Both smack of being clever, which is never a good thing. It’s definitely worth considering whether you could actually just get rid of the type initializer (or part of it) entirely, avoiding maintaining so much static state. It would be nice to be able to detect these type initializer cycles without running anything, simply using static analysis – I’m going to see whether NDepend could do that when I get a chance. The workaround doesn’t feel as neat as Lazy<T>, which is really what’s called for here – but I don’t trust myself to implement it correctly and efficiently myself.

So while both are somewhat hacky, they’re better than the alternative: buggy code. That’s what I’m ashamed to say I had in Noda Time, and I don’t think I’d ever have spotted all the cycles by inspection. It’s worth a try on your own code – see whether you’ve got problems lurking…

 

 

Appendix: Testing code

As promised earlier, here’s the code for the production and test classes.

TypeInitializationChecker

This is in NodaTime.dll itself.

internal sealed class TypeInitializationChecker : MarshalByRefObject
{
    private static List<Dependency> dependencies = null;

    private static readonly MethodInfo EntryMethod = typeof(TypeInitializationChecker).GetMethod("FindDependencies");

    internal static int RecordInitializationStart()
    {
        if (dependencies == null)
        {
            return 0;
        }
        Type previousType = null;
        foreach (var frame in new StackTrace().GetFrames())
        {
            var method = frame.GetMethod();
            if (method == EntryMethod)
            {
                break;
            }
            var declaringType = method.DeclaringType;
            if (method == declaringType.TypeInitializer)
            {
                if (previousType != null)
                {
                    dependencies.Add(new Dependency(declaringType, previousType));
                }
                previousType = declaringType;
            }
        }
        return 0;
    }

    /// <summary>
    /// Invoked from the unit tests, this finds the dependency chain for a single type
    /// by invoking its type initializer.
    /// </summary>
    public Dependency[] FindDependencies(string name)
    {
        dependencies = new List<Dependency>();
        Type type = typeof(TypeInitializationChecker).Assembly.GetType(name, true);
        RuntimeHelpers.RunClassConstructor(type.TypeHandle);
        return dependencies.ToArray();
    }

    /// <summary>
    /// A simple from/to tuple, which can be marshaled across AppDomains.
    /// </summary>
    internal sealed class Dependency : MarshalByRefObject
    {
        public string From { get; private set; }
        public string To { get; private set; }
        internal Dependency(Type from, Type to)
        {
            From = from.FullName;
            To = to.FullName;
        }
    }
}

TypeInitializationTest

This is within NodaTime.Test:

[TestFixture]
public class TypeInitializationTest
{
    [Test]
    public void BuildInitializerLoops()
    {
        Assembly assembly = typeof(TypeInitializationChecker).Assembly;
        var dependencies = new List<TypeInitializationChecker.Dependency>();
        // Test each type in a new AppDomain – we want to see what happens where each type is initialized first.
        // Note: Namespace prefix check is present to get this to survive in test runners which
        // inject extra types. (Seen with JetBrains.Profiler.Core.Instrumentation.DataOnStack.)
        foreach (var type in assembly.GetTypes().Where(t => t.FullName.StartsWith("NodaTime")))
        {
            // Note: this won’t be enough to load the assembly in all test runners. In particular, it fails in
            // NCrunch at the moment.
            AppDomainSetup setup = new AppDomainSetup { ApplicationBase = AppDomain.CurrentDomain.BaseDirectory };
            AppDomain domain = AppDomain.CreateDomain("InitializationTest" + type.Name, AppDomain.CurrentDomain.Evidence, setup);
            var helper = (TypeInitializationChecker)domain.CreateInstanceAndUnwrap(assembly.FullName,
                typeof(TypeInitializationChecker).FullName);
            dependencies.AddRange(helper.FindDependencies(type.FullName));
        }
        var lookup = dependencies.ToLookup(d => d.From, d => d.To);
        // This is less efficient than it might be, but I’m aiming for simplicity: starting at each type
        // which has a dependency, can we make a cycle?
        // See Tarjan’s Algorithm in Wikipedia for ways this could be made more efficient.
        // http://en.wikipedia.org/wiki/Tarjan’s_strongly_connected_components_algorithm
        foreach (var group in lookup)
        {
            Stack<string> path = new Stack<string>();
            CheckForCycles(group.Key, path, lookup);
        }
    }

    private static void CheckForCycles(string next, Stack<string> path, ILookup<string, string> dependencyLookup)
    {
        if (path.Contains(next))
        {
            Assert.Fail("Type initializer cycle: {0}-{1}", string.Join("-", path.Reverse().ToArray()), next);
        }
        path.Push(next);
        foreach (var candidate in dependencyLookup[next].Distinct())
        {
            CheckForCycles(candidate, path, dependencyLookup);
        }
        path.Pop();
    }
}

28 thoughts on “Type initializer circular dependencies”

  1. You wrote “Start initializing First (as we need First.Gamma)”. Isn’t it “Start initializing First (as we need First.Beta)”?

    Like

    Reply

  3. On another note, the image which is supposed to show a number (when you want to submit a comment on this page) doesn’t show…. but if I enter a random number in the ‘enter the numbers above’ field, you seem to receive the comment anyway…

    Like

    Reply

  5. Some thoughts:

    — It seems to me it’s useful to consider there are really two levels of “cyclical dependency” going on here, and that your discussion addresses only one. In particular, the dependency problem here is related to the way that multiple fields in a type are lumped all into a single bucket, but not protected as a single bucket.

    A cyclical dependency where two fields, each in a separate class, depended _directly_ on each other, is still problematic and an impossible bug to fix. You just need a completely different design in that case.

    — In some important ways, this seems to me to be a problem closely related to deadlock in concurrent programming. And in fact, were type initialization order more rigidly enforced at run-time, bugs would be more easily detected, as the program would simply freeze or throw an exception, rather than executing non-deterministically.

    To me, this suggests that the CLI rules for type initialization (in particular, the part you paraphrase regarding what to do if initialization is already in progress for a type in a thread) are flawed and that for program reliability it would actually have been better to disallow re-entrant initialization scenarios.

    By immediately throwing an exception rather than just proceeding blindly, the CLI would follow the “fail fast” approach to reliability. IMHO, it’s better to have an overt, must-fix failure than to have subtle data-corruption problems.

    — Your work-around is IMHO simply a variant on what I’d consider a more-appropriate fix: remove the cycle by moving shared dependency code into a completely different class. The difference being that in your case, your “completely different class” is really just effectively an extension of one of the original classes, whereas I would just break it out into a standalone class.

    I do occasionally find myself running into apparent dependency cycles, and they pretty much always point to an underlying design problem. In particular, a program is much easier to reason about if dependencies are strictly an acyclic graph.

    This comes up with dealing with, for example, assembly dependencies. If I have two assemblies that appear to require references to each other (something that the Visual Studio IDE does not allow, though you can get it to work compiling from the command line), it invariably means that there’s some time in one of those dependencies that really belongs in a third assembly that the original two can reference.

    Likewise, your work-around here shifts initialization into a third type to impose a proper ordering of dependency, but in reality it probably means that that third type really should simply be shared by the original two types. In your example, since First nominally depends on Second, but both types need First.Alpha, the Alpha field probably shouldn’t really be owned by First in the first place.

    And now for some stupid nitpicking… :)

    In the sentence starting with “but often there are natural uses, particular for well-known values…”, I believe you want the word “particularly” instead of “particular”.

    Also, I’d quibble about the claim that this issue is a _classic_ Heisenbug. I agree it falls into the general category, but the fact is that the bug is mostly 100% deterministic for a given program. A _classic_ Heisenbug can disappear on attempts of observation without any overt change in execution order (e.g. concurrency bugs due to timing issues, uninitialized-variable bugs not even possible in .NET, that sort of thing).

    Here, you’ve got a Heisenbug that can disappear only if you actually add new code that changes the order of initialization, or change the order of initialization via for example debugger features.

    Heisenbug? Sure. “Classic”? Nah. :)

    Like

    Reply

  6. Oh yeah, one other thing:

    Your comment about static analysis is IMHO on the money. Run-time analysis is only going to reveal existing cycles, and only to the extent that you can manipulate initialization order to exhaust all the possibilities.

    But using static analysis (e.g. reflection), I believe you should be able to derive a precise dependency graph in which you can detect cycles with 100% reliability.

    In fact, I would think that static analysis would have been _easier_ to implement and, even if not initially easier, would avoid the whole “clutter up production code with testing stubs” business and make it more efficient to apply the analysis to any arbitrary code base.

    Like

    Reply

  7. @Pete: Have fixed the “particular” typo, thanks. I probably started with “in particular” in one construction, then fiddled with the sentence but didn’t correct that part of it. I haven’t changed the Heienbug bit :)

    I agree with you about just about everything else though – and I’d *really* like to have a static analysis approach if possible, but I very much doubt that it’ll be easier to implement. Bear in mind that the cycle can involve several non-type-initializer members in between. With a rather better API than reflection gives us, this may be possible – and I’m still hoping NDepend may do the job – but for the moment, I’m happy enough with what I’ve got and would rather focus on getting Noda Time 1.0 out of the door. Patches with static analysis very welcome :)

    Like

    Reply

  8. You say you don’t want to write Lazy yourself. Are there any reasons not to use the implementation from the mono project?

    Like

    Reply

  10. Well, mono is licensed under the MIT license, so I think you should be able to just copy over their implementation of Lazy without problems.

    Like

    Reply

  11. @Svick: I guess that’s an option. I’ll look into what it would mean in terms of licensing, and whether Lazy{T} itself has any other dependencies.

    Like

    Reply

  12. Have you considered putting all the constants into a single internal static class Contants that would initialize fields in a proper order, avoiding the need for many nested classes?

    Like

    Reply

  13. @configurator: That would require some complex thinking – some of the constants are needed to construct the others, and I wouldn’t like to have to reason about all of that.

    Like

    Reply

  14. I think, since you don’t use explicit static ctors, you might see false positives, because of the specification you quoted (at least in theory). Type initializer of any type that is not yet required could run. With @configurator’s solution at least you can flatten the initialization graph in a deterministic way, but after a few hundred lines of code it might be hard to maintain.

    Like

    Reply

  15. @p4: Yes, the type initializer could run at any time in theory. I don’t see that it will produce *false* positives – just potentially *unexpected* positives. It’s not like I’m forcing the runtime to behave in a different way to how it would normally behave.

    Like

    Reply

  16. My developers love to introduce circular dependencies into our code base. We have some that are so bad that we break code analysis aka FX Cop. We have a two month effort tobget rid of the.To prevent them from introducing any more NDepend is now a required step in code review process.

    NDepend is also useful for determining what to test when we change a method in a library. Looking at the dependency matrix helps focus the testing.

    Like

    Reply

  17. I believe the static analysis approach is exactly an example of where Roslyn may prove invaluable. The required functionality isn’t complete in the CTP, but in due time I may try to implement such a cycle detection algorithm. I think it’d be an excellent exercise

    Like

    Reply

  18. @skeet: For example A class uses B, but B doesn’t have any dependency on A (no cycle here). In theory when you start using B the runtime can load first A then B. Now you have detected a cycle. By using explicit cctors you can have a deterministic initialization, so you can trust you tests better.

    Like

    Reply

  19. @p4: You’ve missed my point – even if it’s not a genuine cycle, if the CLR initializes it *as if* it were a cycle, you’ve still got a problem. Yes, you can use explicit static constructors to remove that – but it’s not really a false positive of “you’ve got a problem” – only a false positive of “it’s a deterministic cycle”.

    To be honest, I think the spec should be tightened up somewhat about when type initializers are allowed to run – at the moment it could fail in all kinds of ways for suitably malevolent (but spec-compliant) implementations.

    Like

    Reply

  20. Typo:
    .. could have declared all these variables as constants instead using “const” …
    should be … using “readonly” …

    This is a great way to find cycles in type initializers.

    Like

    Reply

  21. @Alois: No, that’s not a typo. They’re *already* readonly, but if they’d been declared as true *constants* using const they’d have been resolved at compile time.

    Like

    Reply

  23. Jon,

    I checked, and Mono’s System.Lazy`1 implementation has exactly one dependency on a type not in .Net 3.5, and that is an enum (namely System.Threading.LazyThreadSafetyMode).

    It also has only one dependency on .Net 3.5 relative to .Net 2.0, namely the System.Func`1 delegate.

    Using it in your code would consist solely of:

    * copying two files into your solution
    * adjusting/removing the conditional preprocessor directives
    * adjusting namespaces (as desired)
    * adjusting Visibility (as desired)
    * adding a few lines to the NOTICE file

    That last one is all that must be done to satisfy the license. Specifically, you would need to add a line explaining that part of the code is derived from the mono project, and was originally licensed under the following terms.
    Then you copy and paste the 20 lines of copyright notice and license from one of the files (either one, both are the same).

    Using the word “originally” indicates that you are choosing to sublicense under the Apache license, so that the whole noda-time project covered by one single license (Namely, the Apache license). That is explicitly allowed by the MIT license, as long as the sublicense requires that the notice be kept intact, which the Apachee License does require, per section 4d.

    The two files in question are:
    https://raw.github.com/mono/mono/master/mcs/class/corlib/System/Lazy.cs
    and
    https://raw.github.com/mono/mono/master/mcs/class/corlib/System.Threading/LazyThreadSafetyMode.cs

    Like

    Reply

  24. Is a non-static implementation an option? If static fields are removed and all initialization is done in the constructor, doesn’t the problem go away?

    Like

    Reply

  25. @Robin: The purpose is to expose constants, basically – so no, I can’t move everything to the constructor without losing the benefit.

    Like

    Reply

  26. I know that this post is very old, but I stumbled across the described behavior and I was just wondering what your current approach is. I haven’t found anything in the current version of the Noda Time code that does any cyclic dependency checking.

    Like

    Reply

    1. We don’t have any checks now, as far as I remember – they became too complex to maintain. I believe I simplified the initialization code so that it was less likely to become a problem though.

      Like

      Reply

      1. Thank you for your incredibly quick response, especially to a comment on such an old article! I think this is the way I’ll be going too in my project. Although this is not 100% satisfying to me. But it gives me a bit peace of mind that this is the way that Jon Skeet ended up with after spending much more time on this issue than I have. :)

        Like

        Reply

Leave a comment