[concurrency-interest] Volatile stores in constructors, disallowed to see the default value

Andreas Lochbihler andreas.lochbihler at inf.ethz.ch
Wed Nov 27 08:17:40 EST 2013


Hi Aleksey,

I think that 0 is also an acceptable outcome. In your reasoning, you do not distinguish 
between synchronization order (so) and synchronizes-with order (sw), and only sw if part 
of the happens-before order (hb). The difference is that so orders all access to volatile 
whereas sw only orders writes before subsequent reads, but not reads before (subsequent) 
writes (JLS 17.4.4, 2nd bullet). Consequently, trace A looks as follows:

Trace A: one that reads (r1=0):

   read(a, !null)
      \--po--> vread(a.f, 0)
                    \---so---> vstore(a.f, 42)
                                    \---po---> store(a)

In particular, we don't get vread(a.f, 0) ---hb---> vstore(a.f, 42). Hence, we can commit 
trace A as follows (I write A for the object location of the A object):

1. Commit the initializations a = null, A.f = 0, the initial thread actions, store(a, A).
    read(a, null) sees the initialization a = null
    vread(a.f, 0) actually does not yet exist (if it did, assume it sees A.f = 0)

2. Commit read(a, null), write-seen is as before.

3. Change read(a, null) to now see store(a, A).

    vread(a.f, 0) now executes, so we must add it to the synchronisation order, pick:
    vstore(A.f, null) --so--> vread(A.f, null) --so--> vstore(A.f, 42)

    Hence, vread(a.f, 0) sees vstore(A.f, 0)

    Commit all remaining actions, i.e., vstore(A.f, 42) and vread(A.f, 0).

Andreas

On 27/11/13 13:15, Aleksey Shipilev wrote:
> Hi,
>
> This matter was discussed some time ago privately, but I want to have
> the more rigorous public discussion on this. Let us take the specific
> test as the example. Suppose you have the class:
>
>     class A {
>        volatile int f;
>        A() {
>           f = 42;
>        }
>     }
>
> ...and this test case (note it deliberately omits NPE cases to make
> reasoning simpler):
>
>                   A a;
>     ---------------|----------------
>      a = new A();  |   r1 = a.f;
>
> Except for NPEs, what are the possible values for r1? Both Doug, me, and
> some other folks agree that the only allowed value is {42}, even  though
> it is not evident at first sight, especially if you are contaminated
> with reordering/roach-motel thinking.
>
> The sketch for the proof follows. The surprising consequence of the
> proof below is that roach motel semantics is not always applicable. I
> would be happy to see the flaws in this reasoning or maybe even the
> better proof for this.
>
> In order to answer what outcomes are possible we need to dump the
> usual/partial/misleading "reorderings" and "happens-before" mindset, and
> get to the ground of spec. That is, we need to construct the possible
> traces and see if those traces are committable, as per JLS 17.4.8.
>
> Constructing the traces is arguably easy because we have the volatile
> ops in the trace. It means we can construct two basic traces, for the
> two only juxtapositions of volatile ops in the trace:
>
> Trace A: the one that reads (r1=0):
>
>     vread(a.f, 0)
>             \----sw---> vstore(a.f, 42)
>
> Trace B: the one that reads (r1=42):
>
>     vstore(a.f, 42)
>              \----sw---> vread(a.f, 42)
>
> Now, extending that that skeleton with the program order, will yield two
> final traces:
>
> Trace A: one that reads (r1=0):
>
>   read(a, !null)
>      \--po--> vread(a.f, 0)
>                    \---sw---> vstore(a.f, 42)
>                                    \---po---> store(a)
>
> Note this yields the transitive closure over {po, sw}, and that is
> happens-before:
>
>   read(a, !null)
>      \--hb--> vread(a.f, 0)
>                    \---hb---> vstore(a.f, 42)
>                                    \---hb---> store(a)
>
> Trace B: one that reads (r1=42):
>
>     vstore(a.f, 42)
>       \       \-----------sw------------------> vread(a.f, 42)
>        \                      read(a, !null) ----po----^
>         \----po--->store(a)
>
> Happens-before-wise, this trace only closes over the vstore-vread:
>
>     vstore(a.f, 42)
>               \-----------hb------------------> vread(a.f, 42)
>                               read(a, !null)
>                    store(a)
>
> Now, let's figure out if these traces are committable. You might notice
> the required commit sequence for both these traces are from left to
> right, by accident.
>
> Let us start from the trace B, because it appears simpler. We are
> committing the actions in this order:
>    C0 = {}
>    C1 = C0 union { vstore(a.f, 42) }
>    C2 = C1 union { store(a) }
>    C3 = C2 union { read(a, !null) }  // sees the store(a)
>    C4 = C3 union { vread(a.f, 42) }  // sees the vstore(a.f, 42)
>
> Thus, trace B is committable, and then the behaviors expressed in this
> trace are sound JMM-wise.
>
> Now, let's take the trace A:
>   a) We can not commit read(a, !null) before store(a) is committed,
> because it violates the written values consistency (i.e. V[i]|C[i] =
> V|C[i] in spec).
>   b) We can not commit store(a) before vstore(a.f, 42) is committed,
> because it violates happens-before (i.e. hb[i]|C[i] = hb|C[i] in spec)
> c) We can not commit that vstore(a.f, 42) either because we should
> commit vread(a.f, 0) before, otherwise we violate the written values
> consistency again.
>   d) And in the end, we can only commit vread(a.f, 0) after the read(a,
> !null) is committed, otherwise it violates happens-before again.
>
> Hence, we end up with the causality loop, and this trace is not
> committable. Hence, the result of trace A is not sound JMM-wise.
>
> The only committable trace is trace B, and it yields (r1 = 42).
> Q.E.D.
>
> Thanks,
> -Aleksey.
>
> P.S. Note that if a.f was not volatile, happens-before would not be
> induced, and we will end up with the committable trace yielding (r1=0):
>
>                                           store(a, 42)
>    store(a)
>               read(a, !null)
>                                 read(a, 0)
>
> P.P.S. Doug had this to say in the internal review for this post:
>
> "I think the confusion in this particular case might have arisen years
> ago in a discussion about how you don't actually need a full fence after
> each volatile assignment in code-less constructors (because
> their relative orderings cannot matter), except for the last trailing
> one, which can in turn be weakened to a (final-field style) store fence
> to prevent reorderings wrt actions by the caller. Maybe this
> side-condition became forgotten."
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>


More information about the Concurrency-interest mailing list