Bug in BitMap::par_put_range_within_word

Braun, Matthias matthia.braun at sap.com
Tue Feb 4 11:58:07 UTC 2014


I'd like to report a bug I found in BitMap that has negative effects on G1. More detailed I had reproducible crashes in JBB2013 benchmark with G1 (win x64, VS2010 compiler).
The corrupt java heap was due to heap regions with live data that were scrubbed in final marking phase because their corresponding bit in the region bitmap (ConcurrentMark::_region_bm) were zero, although they were definitely covered by CMCountDataClosureBase::set_bit_for_region.
It finally turned out that BitMap::par_put_range_within_word down the stack of set_bit_for_region for humongous regions actually overwrote some bits of other regions, making the region bitmap invalid.

Reason for that seems to be a missing volatile declaration for pointer 'pw' in this method:

void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
  assert(value == 0 || value == 1, "0 for clear, 1 for set");
  // With a valid range (beg <= end), this test ensures that end != 0, as
  // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
  if (beg != end) {
    intptr_t* pw  = (intptr_t*)word_addr(beg); // FIX: volatile intptr_t* pw  = (volatile intptr_t*)word_addr(beg);
    intptr_t  w   = *pw;
    intptr_t  mr  = (intptr_t)inverted_bit_mask_for_range(beg, end);
    intptr_t  nw  = value ? (w | ~mr) : (w & mr);
    while (true) {
      intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w);
      if (res == w) break;
      w  = *pw;
      nw = value ? (w | ~mr) : (w & mr);

The disassembler (VS2010) showed the reason:

void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
00000000075F7480  mov         qword ptr [rsp+8],rdi
00000000075F7485  mov         rdi,r8
  if (beg != end) {
00000000075F7488  cmp         rdx,r8
00000000075F748B  je          BitMap::par_put_range_within_word+80h (75F7500h)
    intptr_t* pw  =  (intptr_t*)word_addr(beg);
00000000075F748D  mov         r11,qword ptr [rcx+20h]
    intptr_t  w   = *pw;
    intptr_t  mr  = (intptr_t)inverted_bit_mask_for_range(beg, end);
00000000075F7491  movzx       ecx,dl
00000000075F7494  mov         r10,rdx
00000000075F7497  and         cl,3Fh
00000000075F749A  mov         r8d,1
00000000075F74A0  shr         r10,6
00000000075F74A4  mov         edx,r8d
00000000075F74A7  shl         rdx,cl
00000000075F74AA  dec         rdx
00000000075F74AD  and         edi,3Fh
00000000075F74B0  je          BitMap::par_put_range_within_word+40h (75F74C0)
00000000075F74B2  mov         ecx,edi
00000000075F74B4  shl         r8,cl
00000000075F74B7  dec         r8
00000000075F74BA  not         r8
00000000075F74BD  or          rdx,r8
    intptr_t  nw  = value ? (w | ~mr) : (w & mr);
00000000075F74C0  mov         rcx,rdx
00000000075F74C3  test        r9b,r9b
00000000075F74C6  je          BitMap::par_put_range_within_word+51h (75F74D1h)
00000000075F74C8  not         rcx
00000000075F74CB  or          rcx,qword ptr [r11+r10*8]                                                                   // <- calculate nw with the current bitmap state (a)
00000000075F74CF  jmp         BitMap::par_put_range_within_word+55h (75F74D5h)
00000000075F74D1  and         rcx,qword ptr [r11+r10*8]                                                                // <- calculate nw with the current bitmap state (b)
    while (true) {                                                                                                                                             // <- potential bitmap changes here (c), nw now invalid ...
      intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w);
00000000075F74D5  mov         rax,qword ptr [r11+r10*8]                                                               // <- read again from bitmap short before cmpxchg!
00000000075F74D9  lock cmpxchg qword ptr [r11+r10*8],rcx
    bm_word_t mask = inverted_bit_mask_for_range(beg, end);
    *word_addr(beg) &= mask;

The new value 'nw' should be written to the bitmap if and only if (a) or resp. (b) is seen in the atomic swap operation. Instead the operation is performed with an old value 'w' given in register rax, which potentially is filled with  the most latest value of the bitmap (c).  Consequently 'nw' is written to the bitmap discarding all changes made in (c).
After having declared 'pw' as volatile, the disassembly looked ok (and there was no crash anymore ;-).

Depending on the compiler the bug could affect different platforms.

Best regards,
Matthias Braun
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.java.net/pipermail/hotspot-gc-dev/attachments/20140204/3b86d57b/attachment.htm>

More information about the hotspot-gc-dev mailing list