MutabilityDetector is not thread safe #63

Closed
Stephan202 opened this Issue Oct 17, 2015 · 5 comments

Comments

Projects
None yet
2 participants
@Stephan202

The following test fails more than half of the time on my 4 core/8 thread machine (it's an Intel i7-4710MQ CPU).

@Test
public void concurrentMutabilityTest() throws BrokenBarrierException, ExecutionException, InterruptedException {
    final class DummyClass {
        private final ImmutableList<String> list = ImmutableList.of();
        private final ImmutableSortedSet<String> sortedSet = ImmutableSortedSet.of();
    }

    /* Configure the amount of concurrency. */
    final int threads = Runtime.getRuntime().availableProcessors() * 4;
    final int triesPerThread = 10000;

    /* We'll start analysis on multiple threads at roughly the same time. */
    final CyclicBarrier barrier = new CyclicBarrier(threads);
    final ListeningExecutorService es = MoreExecutors.listeningDecorator(Executors.newFixedThreadPool(threads));

    final List<ListenableFuture<List<Throwable>>> futures = new ArrayList<>();
    for (int i = 0; i < threads; i++) {
        futures.add(es.submit(() -> {
            /* Await the start signal. */
            barrier.await();

            /* Repeatedly run the analysis; collect failures. */
            final List<Throwable> failures = new ArrayList<>();
            for (int j = 0; j < triesPerThread; j++) {
                try {
                    MutabilityAssert.assertImmutable(DummyClass.class);
                } catch (final Throwable t) {
                    failures.add(t);
                }
            }

            return failures;
        }));
    }

    /* Wait for all threads to complete, collecting any failures. */
    final Iterable<Throwable> failures = Iterables.concat(Futures.allAsList(futures).get());

    /* Print the failures, if any. */
    failures.forEach(Throwable::printStackTrace);

    /* Fail if there are any. */
    assertEquals(Lists.newArrayList(failures), Lists.newArrayList());
}

When the failure occurs, the following type of stacktrace is logged:

org.mutabilitydetector.unittesting.MutabilityAssertionError:
Expected: com.example.Test$1DummyClass to be IMMUTABLE
     but: com.example.Test$1DummyClass is actually NOT_IMMUTABLE
    Reasons:
        There is a field assigned which creates a circular reference. [Field: sortedSet, Class: com.example.Test$1DummyClass]
    Allowed reasons:
        None.
    at org.mutabilitydetector.unittesting.internal.AssertionReporter.assertThat(AssertionReporter.java:48)
    at org.mutabilitydetector.unittesting.MutabilityAsserter.assertImmutable(MutabilityAsserter.java:108)
    at org.mutabilitydetector.unittesting.MutabilityAssert.assertImmutable(MutabilityAssert.java:672)
    at com.example.Test.lambda$0(AmountTest.java:69)
    at com.google.common.util.concurrent.TrustedListenableFutureTask$TrustedFutureInterruptibleTask.runInterruptibly(TrustedListenableFutureTask.java:108)
    at com.google.common.util.concurrent.InterruptibleTask.run(InterruptibleTask.java:41)
    at com.google.common.util.concurrent.TrustedListenableFutureTask.run(TrustedListenableFutureTask.java:77)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

If MutabilityAssert is not meant to be used concurrently, then that should be documented. But since the default entry point is a static method, I'd argue that concurrent invocations should be supported.

My use case: I use MutabilityAssert quite extensively and run lots of unit tests in parallel, in a single JVM.

What do you think?

@Grundlefleck

This comment has been minimized.

Show comment
Hide comment
@Grundlefleck

Grundlefleck Oct 18, 2015

Contributor

Great test case, it reproduced the problem on my Intel Core 2 Duo laptop. I have committed it to the "client" project, hope you are okay with the project using it.

I've known for a while that Mutability Detector is not thread safe, but the closest that's come to being documented is the name of an internal class, which I agree isn't good enough. Until MutabilityAssert can be made threadsafe, what would you consider the most effective way of documenting that? I would lean towards JavaDoc on the MutabilityAssert class, explained in detail at the class level, and pointers to the doc at the method level. Also perhaps the @NotThreadSafe annotation, described in Java Concurrency in Practice, from the FindBugs jsr305 project, probably on the class level.

The reason I haven't made a bigger deal of it in documentation already is that while I know there is thread unsafety, I wasn't sure how big a deal it would be in practice, and was adopting a Wait And See attitude. Congrats, you're the first caller! :)

Some background on the issue. To my knowledge there is only a single race condition which causes a problem. While there is a lot of internal mutability due to caching, most things that are cached are based on bytecode that doesn't change during a run, so if there is a race to calculate a result, it will be benign. However, in this case, the race condition that causes the failure is due to the implementation of a naive algorithm that detects whether there is a cycle in the types of fields of a class. For example, java.lang.reflect.Constructor has a field of type java.lang.Class and Class has a field of type Constructor. When analysing Constructor, Mutability Detector will check the mutability of the type Class, because generally, every field of an immutable object must be immutable (with caveats). If the analysis has not already completed for Class it will be done on demand. However, while answering the question of whether Class is immutable, it has to find out if Constructor is immutable, because it's the type of one of it's fields, and so it requests the analsysis. This results in a cycle, and in earlier versions would have thrown a StackOverflowException. To avoid this, the analysis "session" keeps track of the requests for an analysis, and if an analysis has already been requested for a class when asked to analyse it again, the algorithm deems that there is a cycle, and returns a result[0] immediately rather than crashing. The mutable state that tracks the requests for analysis is where the race condition is.

By tweaking the settings in your (excellent) test case, there is evidence this is the case. As well as tracking the assertion failure, I also tracked which iteration caused the failure. While it's non-deterministic as you might expect, the failures are only in early runs, in the window before the analysis of DummyClass is completed and cached. Whether there are 100 or 10000 iterations, I never saw it fail later than the 20th iteration, and tended much closer to the 0th iteration. It's also coroborated by only seeing a failure with message There is a field assigned which creates a circular reference, as you mentioned.

All that is to say: yes, Mutability Detector is not thread safe, but I don't think it's a "deep" flaw in the design, it only arises because of one small, specific aspect of design, and it's certainly not a limitation that is irrevocably "baked in".

So, what to do? The cycle detection algorithm should be made thread safe, that's pretty obvious. But until then, documentation should highlight the problem, and a workaround that allows you to run Mutability Detector in multiple threads should be identified. Hopefully you can help me out with suggestions for documentation, and I think there is an approach that will allow you to run tests in parallel in the meantime. Presuming you A) don't mind adding some classes to your source path, and replacing all current calls to MutabilityAssert (hopefully this could be a quick textual search 'n' replace task) and B) your current heap constraints can handle duplication of analysis sessions across threads. The approach uses ThreadLocal analysis sessions, meaning the cycle detection still works on a per-thread basis, but the race condition goes away, with the downside that any cached results are cached once per thread, thus using more memory. I've observed this implementation to pass the test case multiple times, while the original fails,

Three classes are needed for this, which consist of a fairly small change with a lot bit of copy/pasting to keep API and JavaDoc consistent. I've added them here. To use this, include those three classes in your code base, and replace all calls to MutabilityAssert.xxx to ThreadSafeMutabilityAssert.xxx. I think that should solve your immediate problem today, while I consider the best way to solve the problem so that existing calls to MutabilityAssert are thread safe.

How does that sound?

[0] It happens to say that the class is mutable. This is mostly due to erring on the side of caution, rather than the cycle having that impact, since it is possible to have immutable classes with a cycle.

Contributor

Grundlefleck commented Oct 18, 2015

Great test case, it reproduced the problem on my Intel Core 2 Duo laptop. I have committed it to the "client" project, hope you are okay with the project using it.

I've known for a while that Mutability Detector is not thread safe, but the closest that's come to being documented is the name of an internal class, which I agree isn't good enough. Until MutabilityAssert can be made threadsafe, what would you consider the most effective way of documenting that? I would lean towards JavaDoc on the MutabilityAssert class, explained in detail at the class level, and pointers to the doc at the method level. Also perhaps the @NotThreadSafe annotation, described in Java Concurrency in Practice, from the FindBugs jsr305 project, probably on the class level.

The reason I haven't made a bigger deal of it in documentation already is that while I know there is thread unsafety, I wasn't sure how big a deal it would be in practice, and was adopting a Wait And See attitude. Congrats, you're the first caller! :)

Some background on the issue. To my knowledge there is only a single race condition which causes a problem. While there is a lot of internal mutability due to caching, most things that are cached are based on bytecode that doesn't change during a run, so if there is a race to calculate a result, it will be benign. However, in this case, the race condition that causes the failure is due to the implementation of a naive algorithm that detects whether there is a cycle in the types of fields of a class. For example, java.lang.reflect.Constructor has a field of type java.lang.Class and Class has a field of type Constructor. When analysing Constructor, Mutability Detector will check the mutability of the type Class, because generally, every field of an immutable object must be immutable (with caveats). If the analysis has not already completed for Class it will be done on demand. However, while answering the question of whether Class is immutable, it has to find out if Constructor is immutable, because it's the type of one of it's fields, and so it requests the analsysis. This results in a cycle, and in earlier versions would have thrown a StackOverflowException. To avoid this, the analysis "session" keeps track of the requests for an analysis, and if an analysis has already been requested for a class when asked to analyse it again, the algorithm deems that there is a cycle, and returns a result[0] immediately rather than crashing. The mutable state that tracks the requests for analysis is where the race condition is.

By tweaking the settings in your (excellent) test case, there is evidence this is the case. As well as tracking the assertion failure, I also tracked which iteration caused the failure. While it's non-deterministic as you might expect, the failures are only in early runs, in the window before the analysis of DummyClass is completed and cached. Whether there are 100 or 10000 iterations, I never saw it fail later than the 20th iteration, and tended much closer to the 0th iteration. It's also coroborated by only seeing a failure with message There is a field assigned which creates a circular reference, as you mentioned.

All that is to say: yes, Mutability Detector is not thread safe, but I don't think it's a "deep" flaw in the design, it only arises because of one small, specific aspect of design, and it's certainly not a limitation that is irrevocably "baked in".

So, what to do? The cycle detection algorithm should be made thread safe, that's pretty obvious. But until then, documentation should highlight the problem, and a workaround that allows you to run Mutability Detector in multiple threads should be identified. Hopefully you can help me out with suggestions for documentation, and I think there is an approach that will allow you to run tests in parallel in the meantime. Presuming you A) don't mind adding some classes to your source path, and replacing all current calls to MutabilityAssert (hopefully this could be a quick textual search 'n' replace task) and B) your current heap constraints can handle duplication of analysis sessions across threads. The approach uses ThreadLocal analysis sessions, meaning the cycle detection still works on a per-thread basis, but the race condition goes away, with the downside that any cached results are cached once per thread, thus using more memory. I've observed this implementation to pass the test case multiple times, while the original fails,

Three classes are needed for this, which consist of a fairly small change with a lot bit of copy/pasting to keep API and JavaDoc consistent. I've added them here. To use this, include those three classes in your code base, and replace all calls to MutabilityAssert.xxx to ThreadSafeMutabilityAssert.xxx. I think that should solve your immediate problem today, while I consider the best way to solve the problem so that existing calls to MutabilityAssert are thread safe.

How does that sound?

[0] It happens to say that the class is mutable. This is mostly due to erring on the side of caution, rather than the cycle having that impact, since it is possible to have immutable classes with a cycle.

@Stephan202

This comment has been minimized.

Show comment
Hide comment
@Stephan202

Stephan202 Oct 19, 2015

Thanks a lot of the extended response! Of course it's no problem to c/p the test code. :)

Luckily this issue doesn't block us from using MutabilityDetector today, as it happens that we use the utility in only a single unit test in an abstract test class, which is inherited by the unit tests for the relevant model classes. So for the time being I solved the problem simply by wrapping the assertion in a synchronized block.

Very happy to hear the problem is localized to only a single part of the algorithm. I won't have time the coming week(s) to take a closer look, but if it turns out to be a hard one to fix, I might have a crack at it further down the line :)

As for documenting the thread-unsafety in the interim: I'd only go through that trouble if you don't think the code can me made thread-safe before the next release. If that's indeed so, then I guess strictly speaking a warning should be placed on any class and method that a user of the library might use as an "entry point" to the code. Sounds like quite some grunt work. Then again, it might be enough to just place @NotThreadSafe on the relevant classes; any user interested in this topic will probably open the source or JavaDoc and just search for the word "thread". If I'm right about that, then a single hint per class file will do, and the annotation is all that's needed.

Thanks a lot of the extended response! Of course it's no problem to c/p the test code. :)

Luckily this issue doesn't block us from using MutabilityDetector today, as it happens that we use the utility in only a single unit test in an abstract test class, which is inherited by the unit tests for the relevant model classes. So for the time being I solved the problem simply by wrapping the assertion in a synchronized block.

Very happy to hear the problem is localized to only a single part of the algorithm. I won't have time the coming week(s) to take a closer look, but if it turns out to be a hard one to fix, I might have a crack at it further down the line :)

As for documenting the thread-unsafety in the interim: I'd only go through that trouble if you don't think the code can me made thread-safe before the next release. If that's indeed so, then I guess strictly speaking a warning should be placed on any class and method that a user of the library might use as an "entry point" to the code. Sounds like quite some grunt work. Then again, it might be enough to just place @NotThreadSafe on the relevant classes; any user interested in this topic will probably open the source or JavaDoc and just search for the word "thread". If I'm right about that, then a single hint per class file will do, and the annotation is all that's needed.

@Grundlefleck

This comment has been minimized.

Show comment
Hide comment
@Grundlefleck

Grundlefleck Nov 21, 2015

Contributor

Hi @Stephan202,

I have removed the underlying race condition and now consider MutabilityAssert.assertXXX to be thread safe. The state that tracks whether a request for a class is repeated before it's complete, thus indicating a cycle, is now done explicitly by passing that information from the point of the assertion, and is now never shared across threads.

This change will be in version 0.9.6, which I will release after addressing another issue.

In the meantime, is there any chance you could build and test the latest version, and see if your test environment passes without having to resort to using synchronized?

Many thanks again.

Contributor

Grundlefleck commented Nov 21, 2015

Hi @Stephan202,

I have removed the underlying race condition and now consider MutabilityAssert.assertXXX to be thread safe. The state that tracks whether a request for a class is repeated before it's complete, thus indicating a cycle, is now done explicitly by passing that information from the point of the assertion, and is now never shared across threads.

This change will be in version 0.9.6, which I will release after addressing another issue.

In the meantime, is there any chance you could build and test the latest version, and see if your test environment passes without having to resort to using synchronized?

Many thanks again.

@Stephan202

This comment has been minimized.

Show comment
Hide comment
@Stephan202

Stephan202 Nov 21, 2015

@Grundlefleck: Thanks for fixing this! Just tested the latest SNAPSHOT (revision 69fdbd1) and I can confirm the fix works. (To the extend that repeatedly running the tests successfully can be considered "proof", of course!)

@Grundlefleck: Thanks for fixing this! Just tested the latest SNAPSHOT (revision 69fdbd1) and I can confirm the fix works. (To the extend that repeatedly running the tests successfully can be considered "proof", of course!)

@Grundlefleck

This comment has been minimized.

Show comment
Hide comment
@Grundlefleck

Grundlefleck Nov 22, 2015

Contributor

Thanks again @Stephan202. I'll let you know when a release is available.

Contributor

Grundlefleck commented Nov 22, 2015

Thanks again @Stephan202. I'll let you know when a release is available.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment