<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 2.0cm 70.85pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="DE" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US">Hi,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">I’d like to report a bug I found in </span>
<span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">BitMap</span><span lang="EN-US"> that has negative effects on G1. More detailed I had reproducible crashes in JBB2013 benchmark with G1 (win x64, VS2010 compiler).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">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 (</span><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">ConcurrentMark::_region_bm</span><span lang="EN-US">)
were zero, although they were definitely covered by </span><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">CMCountDataClosureBase::set_bit_for_region</span><span lang="EN-US">.
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">It finally turned out that </span><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">BitMap::par_put_range_within_word
</span><span lang="EN-US">down the stack of </span><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">set_bit_for_region</span><span lang="EN-US"> for humongous regions actually overwrote some bits of other regions, making the region bitmap
invalid. <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Reason for that seems to be a missing </span>
<span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">volatile</span><span lang="EN-US"> declaration for pointer ‘pw’ in this method:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New";color:blue">void</span><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> BitMap::par_put_range_within_word(idx_t beg,
idx_t end, <span style="color:blue">bool</span> value) {<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> assert(value == 0 || value == 1,
<span style="color:#A31515">"0 for clear, 1 for set"</span>);<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">
<span style="color:green">// With a valid range (beg <= end), this test ensures that end != 0, as<o:p></o:p></span></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">
<span style="color:green">// required by inverted_bit_mask_for_range. Also avoids an unnecessary write.<o:p></o:p></span></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">
<span style="color:blue">if</span> (beg != end) {<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> intptr_t* pw = (intptr_t*)word_addr(beg); // FIX:
<span style="color:blue">volatile</span> intptr_t* pw = (<span style="color:blue">volatile</span> intptr_t*)word_addr(beg);<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> intptr_t w = *pw;<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end);<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> intptr_t nw = value ? (w | ~mr) : (w & mr);<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">
<span style="color:blue">while</span> (<span style="color:blue">true</span>) {<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w);<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">
<span style="color:blue">if</span> (res == w) <span style="color:blue">break</span>;<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> w = *pw;<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""> nw = value ? (w | ~mr) : (w & mr);<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New"">
</span><span style="font-size:12.0pt;font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span style="font-size:12.0pt;font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">The disassembler (VS2010) showed the reason:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:12.0pt;font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F7480 mov qword ptr [rsp+8],rdi
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F7485 mov rdi,r8 <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> if (beg != end) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F7488 cmp rdx,r8 <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F748B je BitMap::par_put_range_within_word+80h (75F7500h)
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> intptr_t* pw = (intptr_t*)word_addr(beg);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F748D mov r11,qword ptr [rcx+20h]
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> intptr_t w = *pw;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F7491 movzx ecx,dl <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F7494 mov r10,rdx <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F7497 and cl,3Fh <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F749A mov r8d,1 <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74A0 shr r10,6 <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74A4 mov edx,r8d <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74A7 shl rdx,cl <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74AA dec rdx <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74AD and edi,3Fh <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74B0 je BitMap::par_put_range_within_word+40h (75F74C0)
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74B2 mov ecx,edi <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74B4 shl r8,cl <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74B7 dec r8 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74BA not r8 <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74BD or rdx,r8 <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> intptr_t nw = value ? (w | ~mr) : (w & mr);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74C0 mov rcx,rdx <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74C3 test r9b,r9b <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74C6 je BitMap::par_put_range_within_word+51h (75F74D1h)
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74C8 not rcx <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74CB or rcx,qword ptr [r11+r10*8] // <- calculate nw with the current bitmap state (a)
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74CF jmp BitMap::par_put_range_within_word+55h (75F74D5h)
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74D1 and rcx,qword ptr [r11+r10*8] // <- calculate nw with the current bitmap state (b)<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> while (true) { // <- potential bitmap changes here (c), nw now invalid …<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74D5 mov rax,qword ptr [r11+r10*8] // <- read again from bitmap short before cmpxchg!<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">00000000075F74D9 lock cmpxchg qword ptr [r11+r10*8],rcx
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> bm_word_t mask = inverted_bit_mask_for_range(beg, end);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> *word_addr(beg) &= mask;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> }<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">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).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">After having declared ‘pw’ as volatile, the disassembly looked ok (and there was no crash anymore ;-).<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Depending on the compiler the bug could affect different platforms.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Best regards,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Matthias Braun<o:p></o:p></span></p>
</div>
</body>
</html>