RFR: 8225716: G1 GC: Undefined behaviour in G1BlockOffsetTablePart::block_at_or_preceding

[Andrew Haley]

The Block Offset Table is accessed racily in many places. This is UB,
but I suspect the authors of G1 assumed that the UB was "benign". In
fact it is not, and there is a narrow race condition which causes G1
to crash at times of heavy stress.

The bug has only ever been observed on 86-32, but it isn't a
target-specific bug. It's probably not specific to G1 either.

The problem occurs when the BOT is updated by one thread while it's
being read by another. The BOT isn't volatile, so a C++ compiler is
entitled to transform this code:

  uint offset = _bot->offset_array(index);  // Extend u_char to uint.
  while (offset >= BOTConstants::N_words) {
    // The excess of the offset from N_words indicates a power of Base
    // to go back by.
    size_t n_cards_back = BOTConstants::entry_to_cards_back(offset);
    q -= (BOTConstants::N_words * n_cards_back);
    index -= n_cards_back;
    offset = _bot->offset_array(index);
  }

into

  while (_bot->offset_array(index) >= BOTConstants::N_words) {
    // The excess of the offset from N_words indicates a power of Base
    // to go back by.
    size_t n_cards_back
      = BOTConstants::entry_to_cards_back(_bot->offset_array(index));
    q -= (BOTConstants::N_words * n_cards_back);
    index -= n_cards_back;
  }

But if someone is modifying _offset_array then this code is no longer
correct. We first read the offset, see that we have to slide back N
cards, and then we read the (changed) offset and slide back the wrong
(and huge) nuber of cards, and a crash is the inevitable result. It's
a matter of luck that this hasn't happened before now.

Making the BOT volatile would probably fix this, but IMO it makes more
sense to make the access explicit:

u_char G1BlockOffsetTable::offset_array(size_t index) const {
  check_index(index, "index out of range");
  return Atomic::load(&_offset_array[index]);
}

void set_offset_array_raw(size_t index, u_char offset) {
  Atomic::store(offset, &_offset_array[index]);
}

http://cr.openjdk.java.net/~aph/8225716/

-- 
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
https://keybase.io/andrewhaley
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671