RFR (S) 8078438: Interpreter should support conditional card marks (UseCondCardMark)

[Andrew Dinn]

On 29/04/15 10:51, Andrew Haley wrote:
> There is still something I don't understand.
> 
> Let's imagine that the card is already marked 0.  We're using
> conditional card marks, so we don't write another 0 to the card table.
> 
> Mutator:                CMS-preclean:
> # o.x == NULL
> # card[o >> 9] == 0x0
> o.x = a
>                         finds card[o >> 9] == 0x0
>                         reads o.x, finds NULL
>                         writes card[o >> 9] = 0x1
> #                       o.x == a becomes visible
> 
> Isn't this exactly the same problem?

Yes, I agree the problem is still there whatever means the mutator uses
to order its card mark after the associated write. A missing element in
the picture above is where the conditonal mark gets done. Let's redraw
it and add some (cpu-local) timestamps:

Mutator:                CMS-preclean:
T0_a:
o.x == NULL

T1_a:
if card[o >> 9] == 0x1
  card[o >> 9] = 0x0

T2_a:
o.x = a
                        T1_b:
                        finds card[o >> 9] == 0x0

                        T2_b:
                        reads o.x, finds NULL

                        T3_b:
                        writes card[o >> 9] = 0x1

T3_a:
if card[o >> 9] == 0x1
  card[o >> 9] = 0x0

                        T4_b:
                        o.x == a becomes visible

Whether we rely on TSO or on a releasing store to do the card mark all
that ensures is that when the GC thread sees card[o >> 9] == 0x0 at time
T1_b it must also see either o.x == NULL or, possibly, o.x == a.

There is nothing to guarantee the GC thread sees the write to a at this
point (i.e. we cannot claim that T2_b > T2_a). So we can legitimately
assume that it sees NULL and goes on to write 0x1 to the card.

But then neither is there anything to guarantee that the conditional
test at T3_a sees the write of 0x1 at T3_b. We know T3_b > T1_a but that
is all. The mutator and GC thread would have to employ some sort of
ordering relationship between the write at T3_b and the read at T3_a to
guarantee that. TSO won't do it. Nor will an stlr at T1_a.

Of course, if the mutator writes the card unconditionally at T3_a then
there is no problem -- the GC will see the dirty card at the next dirty
scan. The problem is that the condition test may be based on out of date
information causing a necessary card mark to be omitted.

regards,


Andrew Dinn
-----------