Safe Publication Of Transient Members

2012-12-17 06:33UTC

A very common (and quite dangerous) tripping point I find in concurrent Java code is that of unsafe member publication of otherwise safely-published objects. Of course, concurrent code is difficult to get right and I occasionally find myself identifying the same mistake in my own code---but usually only after a restful night of sleep. Hence, I write this article with the intent of keeping this problem at the front of my mind. Prior to continuing, readers unfamiliar with the concept of "safe publication" should familiarize themselves with the literature listed in the final section, Further Readings, of this article.

What, exactly, do I mean, "safe publication of transient members?" I refer specifically to mutation of an instance field, a, of an object instance, o (syntactically, o.a), which has been safely published. Recall that safe publication may be achieved in several ways: through the use of an atomic reference, a final field, a volatile field, a monitor, or other similar mechanism; also recall that safe publication is a one-time event: any mutations to an object, o, safely published in method x may not be safely published in method y. Therein lies this problem.

One common safe publication technique is a concurrent collection, such as the ConcurrentHashMap, which uses a hodgepodge of finals, volatiles, and Unsafe magic to guarantee object visibility: writes from thread A happen-before reads in thread B (assuming, of course, thread A naturally proceeds thread B and thread B does not preempt thread A). For example, in the following code block, if thread A invokes write("a", new Object()) prior to thread B invoking read("a"), thread B is guaranteed to see o in a state as-up-to-date as that visible to thread A at the time of invoking write(...). This means that o has been safely published through SafePublication.m.

public final class SafePublication
{
    private static final ConcurrentMap<String, Object> m = new ConcurrentHashMap<>();

    public static void write(final String key, final Object o)
    {
        m.put(key, o);
    }

    public static Object read(final String key)
    {
        return m.get(key);
    }
}

Since Object is a very simple class, the above example does not demonstrate the subject of this article. Consider, instead, the slightly more complex class, SingleMember, which has a single integer member, i:

public final class SingleMember
{
    private int i;

    public SingleMember(final int i)
    {
        this.i = i;
    }

    public final int get()
    {
        return this.i;
    }

    public final void increment()
    {
        this.i++;
    }
}

With consideration to SingleMember, thread A invoking write("a", new SingleMember(10)), followed by thread B invoking read("a"), thread B is guaranteed to get an instance of SingleMember, s, where s.i == 10. At this point in time, s.i is "effectively immutable"---all reads of s, at least when accessed through SafePublication.m will see s.i == 10.

Next, consider thread C invokes the following code:

SafePublication.read("a").increment();

At this time, by definition, s.i is no longer "effectively immutable" since it has been mutated. Semantics change and, interestingly, neither thread A nor thread B are guaranteed to read s.i == 11 and may still read s.i == 10; however, due to sequential consistency guarantees, thread C is guaranteed to see s.i == 11. Indeed, threads A and B may see s.i == 11, but, according to the Java Memory Model, there is no guarantee.

A Full Example

At this point, you're probably frustrated about all the previous meta-code. To demonstrate the problem, the following is an executable example. Differences in hardware and JREs may result in different execution of the following block. Run on an Intel x86_64 processor with Java 6 or 7, the following code will likely enter an infinite loop and block indefinitely, perhaps after printing a couple lines. Other processors or JREs may result in different behaviour (the example may possibly even work in a seeming-sequential way).

public final class SafePublication
{
    private static final ConcurrentMap<String, SingleMember> m = new ConcurrentHashMap<>();

    static final class SingleMember
    {
        private int i = 0;

        public SingleMember(final int i)
        {
            this.i = i;
        }

        public final int get()
        {
            return this.i;
        }

        public final void increment()
        {
            this.i++;
        }
    }

    static final class ThreadB implements Runnable
    {
        @Override
        public void run()
        {
            final SingleMember d = SafePublication.read("a");
            while(d.get() < 11);
        }
    }

    static final class ThreadC implements Runnable
    {
        @Override
        public void run()
        {
            SafePublication.read("a").increment();
        }
    }

    public static void write(final String key, final SingleMember s)
    {
        m.put(key, s);
    }

    public static SingleMember read(final String key)
    {
        return m.get(key);
    }

    public static void main(final String[] args) throws InterruptedException
    {
        for(int i = 0; i < 20; i++){
            // This  is effectively thread A.
            SafePublication.write("a", new SingleMember(10));
            final Thread b = new Thread(new ThreadB());
            final Thread c = new Thread(new ThreadC());

            b.start();
            // Ensure the loop has been started.
            Thread.sleep(50);
            c.start();

            // Beyond this join point, thread A is guaranteed to see s.i == 11.
            c.join();
            b.join();
            System.out.println(SafePublication.read("a").get());
        }
    }
}

So, what's going on? Simply, something in the system, whether it be the Java JIT compiler, processor(s), processor cache(s), etc, is storing a copy of s.i---likely for performance reasons. Specific reasons are out of scope of this article; however, numerous articles online cover this topic in further depth. When thread B reads s from m, s.i is not guaranteed to be anything but 10; thus, the JVM or hardware may freely "optimize" our code (in the crudest sense, consider it looping on the constant condition, while(10 < 11)). Sadly, this code is wrong, even though it may look right and, sometimes, may even seem to behave correctly.

To be absolutely clear, mutation of members of s must be safely published (and, accordingly, safely consumed). Even though accessing s via m is considered safe, accessing s.i is not. Ultimately, the compiler (thus hardware) is free to cache or reorder reads and writes of s.i regardless of s.

Solutions

In general, the solution is to ensure the safe publication of all members of s. Thankfully, numerous solutions exist to solve this problem. In-depth explanation is not in scope of this article, but a summary follows:

Immutability

Immutability is, by far, the simplest and, arguably, best solution to guarantee an object's member is safely published. In Java, immutable (or final) members are guaranteed to be safely published (hence visible) once the object's constructor is complete. Recall, however, that final members with their own non-final members are still a problem.

Unfortunately, in this specific example, an immutable member, s.i, does not solve the problem, as s.i is inherently mutable.

Volatile Members

Volatile members, for example, enforce a sequential-like consistency guarantee such that writes that happen-before reads to a location must be visible to all threads. While volatile members work well for atomic writes, you, the astute reader, have probably noticed the increment() is non-atomic: it uses the compound operation getfield->iconst->iadd->putfield. This means we may (especially with high contention) see lost updates that result in the very same behaviour as the original problem (but for different reasons).

Atomic Types

Substituting the primitive, SingleMember.i, with an AtomicInteger fixes this problem, as the reads and writes are properly fenced by volatiles and more Unsafe magic encapsulated within the AtomicInteger. This nicely solves the problem and, realistically, does not change the semantics of this code.

Be cautious you do not accidentally confuse the need for an atomic operation (possibly requiring mutual exclusion or compare-swap implementation) with the need for a simple atomic type.

Monitors

A shared monitor on each method accessing SingleMember.i (specifically, SingleMember.increment() and SingleMember.get()) will resolve this issue: a fence around both read and write is required to instruct the compiler that it is not free to "optimize" the read or write. Marking both methods as synchronized, for example, would be sufficient. This significantly changes the access semantics of SingleMember.i, which is no longer accessible concurrently.

Republish s

Finally, republishing s after mutating s.i will allow other threads to properly see the changes (as of JRE5). Note, still, that in the above example, the effective hoisting of SafePublication.read("a") will still prevent republication from properly resolving this issue. Indeed, the read(...) invocation must be brought into the loop. Otherwise, the JVM and/or hardware may still cache or reorder reads of the now (possibly) local members members of s.

Conclusion

This article identifies design mistakes in accessing mutable members of safely published objects. This is an easy mistake to make and a difficult mistake to diagnose.

In general, whenever an object is shared between threads, pay attention to all its members, and each of those members' members, etc.

Further Readings