The JMM is too weak

Joshua Bloch of Javasoft was one of the first to recognize that many of the idioms used in writing Java programs were not guaranteed to be safe according to the JMM. Consider the example in Figure 9. The JMM given in [GJS96, Chap 17] doesn't require that the writes initializing the point allocated by thread 1 be sent to main memory before the write of the reference to the newly created point into p, nor does it require that the read of p.x be done after the read of p.

This is rather unpleasant. For one things, final fields aren't final. Even if a field is declared as a final, this loophole could allow another thread accessing the object might see the default value for the field. In all kinds of code, you would need to worry about whether the object a method is invoked on is properly initialized.

  

Figure 10: Synchronized reordering of field initialization and ref update

  

Figure 11: More synchronization doesn't help

Note that synchronization isn't a magic fix to this problem. If we add synchronization to the update, but not to the read (as in Figure 10), we still have the exact same problem; both all writes need to be sent to main memory before the unlock action, but they can be sent in any order. You might think that putting a monitorexit between the creation of the Point and the storing of the Point into this.p might fix the problem; this is equivalent to making the constructor synchronized (see Figure 11). Unfortunately, this doesn't fix the problem either, because in the existing JMM, the write to this.p can be moved above the monitorexit instruction. The only way to fix this in the existing JMM is to require that the reader be synchronized.

Now of course, you can always say ``Don't write code with race conditions!'' But if you were writing a library that was sensitive from a security viewpoint, you would have to worry about other programmers using race conditions to attack your code. To fix this, we probably need to make all of the getFoo() methods synchronized (a getFoo() method is one that provides controlled access to a field/attribute Foo of an object). In the java.*, java.*.* and java.*.*.* packages of Sun's 1.2 distribution, there are a total of 829 getFoo() methods that return object references, of which only 26 are synchronized. Also, encouraging programmers to be very aggressive about using synchronization could also introduce more problems with deadlock.

  

Figure 12: Double-check and lazy instantiation idioms

Another example of a programming idiom that is unsafe according to the current JMM is the double-check and lazy instantiation idioms, described in a recent article [BW99b] and book [BW99a, Chap. 9]. Figure 12 shows this idiom. This idiom is unsafe because the writes that initialize the MessageBox don't need to be sent to main memory before the storing of the reference to the MessageBox into mb.

I am convinced that we must fix this problem by making it possible to enforce an order on the writes. Trying to solve this problem solely by requiring synchronization whenever accessing shared data just isn't going to work.

I don't believe that there are any current Java implementations that could exhibit the behavior shown in Figures 9 - 11. As a result, few developers would bother avoiding idioms like that, feeling confident that they won't get bit. However, with advanced optimizing compilers and aggressive architectures, we might see this behavior down the road, at which point a huge codebase of unsafe code will exist.

Before trying to fix the problem, we should explore it in more detail. The basic problem in Figure 9 is that there are two writes to global memory that can be reordered, either by compiler optimizations or by the processor. There is no dependence forcing one write to come after the other, so the ordering is feasible and plausible unless we forbid it. If these writes are reordered, it could be detected by other threads, possibly with severe consequences. The reads might also be reordered, but this is more difficult because the memory location read by the second read is dependent on the value read by the first read.

In addition to arising in constructors, as shown in Figures 9 - 11, it also arises in the situations shown in Figures 13 - 15. If we are going to prohibit the anomalous behavior in Figures 9 - 11, we should also examine the behavior in Figures 13 - 15 and decide if they need to be prohibited.

I am not going to give a definitive answer. Instead, I will suggest several solutions, and discuss which behaviors they prohibit and their potential impact on compiler optimizations. My suggestions are roughly ordered from least protection/least cost to highest protection/highest cost, except making unlock a bidirectional write-barrier, which I consider a necessary prerequisite.

Unlock must be a bidirectional write-barrier

The first fix that must be made to allow an ordering constraint to be imposed on writes. The existing JMM [GJS96, §17.6] prohibits moving a store/write to after an unlock action, but it doesn't prohibit a store/write from being moved to before an unlock action. The existing JMM can be patched by making an unlock action act as a bi-directional store/write barrier. In my proposed new Java memory model, I have already make this change (item 3 of Section 4).

Once this change is made, Figure 11 can no longer exhibit anomalous behavior. You might try to fix the problems in Figures 9 - 10 by declaring the constructors as synchronized. Unfortunately, that isn't legal in Java. Without additional changes, the only solution would be to put synchronized blocks inside in each constructor. This would work, but it would be a substantial pain.

  

Figure 13: Reordering of field update and ref update

  

Figure 14: Reordering of element update and ref update

Don't do that

The easiest solution is to say ``Don't write programs with race conditions'', and to not prohibit any of the anomalous behavior. Although I think that people need to be much more leery of race conditions than many are, I don't recommend this approach. Among other problems, a package developer would have to worry too much about whether users were avoiding data races. A developer could put synchronized blocks inside constructors to prohibit the behavior of Figures 9 - 10 on a case-by-case basis, but I suspect few developers would.

Allowing constructors to be synchronized

By allowing programmers to specify that a constructor is synchronized, a developer could, on a case-by-case basis, prohibit the behavior in Figures 9 -10 . This would be easier than putting synchronized blocks in constructor methods, but still I suspect few developers would bother doing so.

Ordering writes across a constructor completion

We could add the following rule to the set given in Section 4

a

if A and B are both write actions, A writes to a field of an object X, B writes X into some variable, A occurs during some constructor C invoked to create X, and B occurs after C finishes, then there is a direct dependence ordering between A and B and they cannot be reordered.

Note that since there isn't (and shouldn't be) any action corresponding to a completion of a constructor, keeping track of this requirement requires more than just looking at the actions. In particular, if a constructor has been inlined, then forcing the appropriate ordering constraints might require forcing some sort of memory barrier (as in Section 5.4).

This will complete prohibit the behavior Figure 9. It won't completely prohibit seeing pre-initialized values for final fields. If a constructor passes this to another method before all of the final fields are initialized, the other method can see them (but this is an evil programming style). This doesn't prohibit any of the behavior in Figures 13 - 15.

   
Forcing a write barrier after a constructor call

We could say that the completion of a constructor call acts as a special barrier action, and add the rule:

b

if A and B are a write action and a barrier action (either order), then there is a direct dependence ordering between A and B and they cannot be reordered.

The virtual machine could enforce a rule that the completion of a constructor acted as a write barrier, in the same way as a unlock action. This could apply to all constructors, or the spec might only require a write barrier at the completion of the outermost constructor (although putting one at the completion of every constructor would be allowed).

This is similar to allowing constructors to be synchronized. But since it doesn't actually lock the object, it couldn't possibly cause deadlock and would likely have minimal effects on performance. Thus, we don't have to worry about which constructors to synchronize; we just force a write barrier after every object is constructed. It also doesn't force a thread to empty the thread's working memory, so it may be less expensive than synchronization.

This approach is a little simpler to explain than rule a above, since it is simply explained in terms of actions. However, in code that created lots of light weight objects (particularly if the Java language is changed to provide better support for light weight objects than can be unboxed), the large number of memory barriers generated could significantly reduce the transformations that could be applied to the program.

Ordering writes

If we want to prohibit the anomalous behavior in Figures 13 - 14, we can do it by imposing constraints on the reordering of writes (the reordering of the reads in these examples is prohibited by the data dependence between the two reads).

We have a couple of options as to how strong we want this constraint to be. The basic, strong form of it is:

c

if A and B are both write actions, A writes to a field or element of an object X, B writes X into some variable, then there is a direct dependence ordering between A and B and they cannot be reordered.

This would prohibit the anomalous behavior in Figures 9 - 14. We can relax this with any combination of the following two options:

1.

Enforce c only if the A writes is to a field, not an element.

2.

Enforce c only if the B writes X to a volatile variable.

One of the problems with enforcing this ordering is that we have to enforce it whenever a write might be to a field/element of an object being stored by the later write. Others I discussed this with expressed the opinion that this constraint should only be enforced if the writes involve the same variable, so that you know they reference the same object. In other words, if I write to p.x, then I write p into some variable, then I can't reorder the writes. However, if I write to p.x, and then I write q into some variable, than I can reorder them even though p and q might reference the same object. The problem with basing this constraint on variable names is that while variable names are fairly obvious in Java source code, they are not present in the Java virtual machine. When writing p, the value being stored comes off of the stack and might have gotten there through any number of stack manipulation instructions. Defining this constraint so that it only enforced the constraint when the same ``variable'' is involved would be very difficult to define and implement at the JVM level.

A decision to enforce one of these constraints should not be made without an understanding of the performance impact. Particularly due to the problem with aliases, the impact could be substantial (e.g., you would pretty much have to insert a write barrier before any store of an java.lang.Object, because it might reference any object that you have previously updated.

If we enforce this constraint only when the second write is to a volatile field, I suspect the performance impact will not be substantial. It makes a certain amount of sense, because if you are playing with data races, making your variables volatile is appropriate.

  

Figure 15: Reordering of element update and index update

Prohibit all write reorderings

If you want to prohibit the anomalous behavior in Figure 15, I think you would really have to prohibit all write reorderings. But I don't think this should be seriously considered. This example is just a straw man to suggest that we are going to have to accept some anomalous behavior due to write reordering.