Possible deadlock in ImmutableList

[kronar]

ImmutableList contains following code since version 15.0

private static final ImmutableList EMPTY =
new RegularImmutableList(ObjectArrays.EMPTY_ARRAY);

[cpovirk]

Can you elaborate on the deadlock? I guess the idea is that one thread starts to load ImmutableList while the other starts to load RegularImmutableList? That's probably not good, though we may have this problem in a lot of places, and I haven't heard reports of trouble... yet...

[apangin]

Here is the minimal test case I could create. It hangs intermittently.

public static void main(String[] args) throws Exception {
    new Thread() {
        public void run() {
            ImmutableList.of();
        }
    }.start();

    Thread.sleep(1);

    Class.forName("com.google.common.collect.RegularImmutableList");
}

The problem is not just theoretical - we've hit the real deadlock in a large production deployment.

[cpovirk]

Sorry, I missed the last part of your message (about how you've hit this in prod). That makes more much more worried about this.

Part of the reason I'm worried is that we might have these cycles in lots of places. I'll fix this one, but we may have others. Maybe we should write a test that loads each of our classes in a new, instrumented ClassLoader. I'm always in over my head with ClassLoader, but I'm hoping that maybe we can override loadClass to record all classes loaded during the loading of the class. Then we can build a graph and look for cycles. If they're all over, we may just wait for reports to come in.... Hopefully there would be a manageable number.

[cpovirk]

ClassLoader is probably the wrong approach. @lukesandberg suggests that ASM may help. For now, though, I'm dropping this.

(The specific problem of RegularImmutableList has been fixed internally, so it will be mirrored out soon.)

[cpovirk]

Thought about this a little more today.

One subtlety here is how the app starts to initialize RegularImmutableList without first initializing ImmutableList. How does the app get at package-private RegularImmutableList except through ImmutableList? Well, it turns out that Guava calls directly into RegularImmutableList in places outside ImmutableList. For example, ImmutableSortedMap.fromEntries does this.

Until then, I had hoped that I could restrict my search to classes that involve clinit from at least 2 public (or protected) classes. (It turns out, as expected, that Guava has a lot of cycles that involve non-public classes.) But if I restrict myself to cases in which at least 2 of the classes involved are public, I miss the ImmutableList problem.

But if I turn off the restriction, again, I get many results, most of which are false positives. But to actually determine which are true positives, I'd have to soup up the analyzer. I think I need to find cases where we can get from a public/protected API into a clinit for a class? This sounds like a mess.

Given that, I think I'll just go after the high-visibility classes with potential problems: ImmutableSortedMultiset, ImmutableSortedSet, and ImmutableTable. We should probably follow the ImmutableList pattern there if only to set a good example for ourselves.

[cpovirk]

To detect any remaining or new problems, we could look at ArchUnit for its Cycle Checks (mentioned in #4011 (comment)).

[edit: Oops, sorry, I think ArchUnit is talking about a different kind of cycle, so it's unlikely to help here.]

[vlsi]

I've requested ArchUnit sample via TNG/ArchUnit#470
An alternative option is https://github.com/jQAssistant/jqassistant which loads the model to Neo4j, then assertions could use cypher queries.

[carterkozak]

@cpovirk I've built an errorprone check which detects precisely this kind of deadlock here: palantir/gradle-baseline#1598

I'd be more than happy to transfer the code upstream into error-prone if there's interest.

[cpovirk]

Thanks! I am interested in principle. My fear has been that such a checker may be prone to false positives, but if they turn out to be easy enough to work around, we'd probably enable a check anyway as a precaution.

[carterkozak]

I've added an error-prone ticket to discuss upstreaming the check: google/error-prone#2062