<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 12pt;
font-family:Calibri
}
--></style></head>
<body class='hmmessage'><div dir='ltr'>The processor can reorder. Across call/ret at least in general.<br><br><br>The compiler can also reorder, if you have whole-program-optimization, link-time-code-gen (Microsoft "LTCG"), link-time-optimization (gcc "LTO"). (We don't, but real world systems certainly do.)<br><br><br> - Jay<br><br><br><div><div id="SkyDrivePlaceholder"></div>> To: jay.krell@cornell.edu; m3devel@elegosoft.com; mika@async.caltech.edu<br>> Subject: Re: [M3devel] race conditions in lock-free code...<br>> Date: Sun, 26 Aug 2012 22:32:48 -0700<br>> From: mika@async.caltech.edu<br>> <br>> Sorry, I can't seem to quote your message.<br>> <br>> You say that Text8.New's result can be assigned to fromCharCache[c]<br>> before Text8.New is done running. How is that possible? Surely<br>> Text8.New has to calculate its result before it can be assigned<br>> anywhere. Yes possibly FromChar allocates space for the result of<br>> Text8.New but the assignment of whatever appears in that space can't<br>> happen until *after* Text8.New has run. Unless you are saying that<br>> the running of Text8.New and FromChar are intertwined somehow..?<br>> I know compilers do some odd things but that doesn't sound right...<br>> <br>> If Text8.New took fromCharCache[c] as a VAR parameter you might be<br>> right, though. But it doesn't...<br>> <br>> Am I missing something?<br>> <br>> Mika<br>> <br>> Mika Nystrom writes:<br>> ><br>> >Yeah it's a race condition, in theory. But is it important? If you get<br>> >the wrong copy, there will be two TEXTs representing one CHAR. But no<br>> >one ever said FromChar was guaranteed to return the same pointer when<br>> >you call it with the same CHAR...<br>> ><br>> > Mika<br>> ><br>> >Jay K writes:<br>> >>--_5f23896e-68ee-44da-82dd-311cd8c58979_<br>> >>Content-Type: text/plain; charset="iso-8859-1"<br>> >>Content-Transfer-Encoding: quoted-printable<br>> >><br>> >>We have race conditions=2C like this=2C m3core/src/Text.m3:<br>> >><br>> >><br>> >>VAR fromCharCache :=3D ARRAY CHAR OF T {NIL=2C ..}=3B (* 1-char texts *)<br>> >><br>> >><br>> >>PROCEDURE FromChar (c: CHAR): T =3D<br>> >> VAR buf: ARRAY [0..0] OF CHAR=3B<br>> >> BEGIN<br>> >> IF fromCharCache [c] =3D NIL THEN<br>> >> buf [0] :=3D c=3B<br>> >> fromCharCache[c] :=3D Text8.New (buf)=3B<br>> >> END=3B<br>> >> RETURN fromCharCache [c]<br>> >> END FromChar=3B<br>> >><br>> >><br>> >>It should be:<br>> >><br>> >><br>> >>PROCEDURE FromChar (c: CHAR): T =3D<br>> >>=0A=<br>> >> VAR buf: ARRAY [0..0] OF CHAR=3B<br>> >>=0A=<br>> >> BEGIN<br>> >>=0A=<br>> >> IF fromCharCache [c] =3D NIL THEN<br>> >>=0A=<br>> >> buf [0] :=3D c=3B<br>> >>=0A=<br>> >> WITH a =3D Text8.New (buf) DO<br>> >> MemoryBarrier()=3B<br>> >> fromCharCache[c] :=3D a=3B<br>> >> END=3B<br>> >>=0A=<br>> >> END=3B<br>> >>=0A=<br>> >> RETURN fromCharCache [c]<br>> >>=0A=<br>> >> END FromChar=3B<br>> >>=0A=<br>> >><br>> >><br>> >>to ensure that all of Text8.New() finishes before the assignment to fromCha=<br>> >>rCache[c] is made.<br>> >><br>> >><br>> >>Can the compiler somehow catch these?<br>> >>I fear they are a small epidemic.<br>> >>For a long time people didn't realize where all the compiler and processor =<br>> >>could reorder.<br>> >><br>> >><br>> >>Do we have the right constructs by now to fix them?<br>> >>I think we do.<br>> >><br>> >><br>> >> - Jay<br>> >> =<br>> >><br>> >>--_5f23896e-68ee-44da-82dd-311cd8c58979_<br>> >>Content-Type: text/html; charset="iso-8859-1"<br>> >>Content-Transfer-Encoding: quoted-printable<br>> >><br>> >><html><br>> >><head><br>> >><style><!--<br>> >>.hmmessage P<br>> >>{<br>> >>margin:0px=3B<br>> >>padding:0px<br>> >>}<br>> >>body.hmmessage<br>> >>{<br>> >>font-size: 12pt=3B<br>> >>font-family:Calibri<br>> >>}<br>> >>--></style></head><br>> >><body class=3D'hmmessage'><div dir=3D'ltr'>We have race conditions=2C like =<br>> >>this=2C m3core/src/Text.m3:<br><br><br>VAR fromCharCache :=3D ARRAY CHAR OF=<br>> >> T {NIL=2C ..}=3B (* 1-char texts *)<br><br><br>PROCEDURE FromChar (c: CHAR=<br>> >>): T =3D<br> =3B VAR buf: ARRAY [0..0] OF CHAR=3B<br> =3B BEGIN<br>=<br>> >> =3B =3B =3B IF fromCharCache [c] =3D NIL THEN<br> =3B =<br>> >>=3B =3B =3B =3B buf [0] :=3D c=3B<br> =3B =3B =3B&n=<br>> >>bsp=3B =3B fromCharCache[c] :=3D Text8.New (buf)=3B<br> =3B =3B=<br>> >> =3B END=3B<br> =3B =3B =3B RETURN fromCharCache [c]<br>&nb=<br>> >>sp=3B END FromChar=3B<br><br><br>It should be:<br><br><br>PROCEDURE FromCha=<br>> >>r (c: CHAR): T =3D<br>=0A=<br>> >> =3B VAR buf: ARRAY [0..0] OF CHAR=3B<br>=0A=<br>> >> =3B BEGIN<br>=0A=<br>> >> =3B =3B =3B IF fromCharCache [c] =3D NIL THEN<br>=0A=<br>> >> =3B =3B =3B =3B =3B buf [0] :=3D c=3B<br>=0A=<br>> >> =3B =3B =3B =3B =3B WITH a =3D Text8.New (buf) DO<br>&=<br>> >>nbsp=3B =3B =3B =3B =3B =3B =3B MemoryBarrier()=3B<=<br>> >>br> =3B =3B =3B =3B =3B =3B =3B fromCharCache[c=<br>> >>] :=3D a=3B<br> =3B =3B =3B =3B END=3B<br>=0A=<br>> >> =3B =3B =3B END=3B<br>=0A=<br>> >> =3B =3B =3B RETURN fromCharCache [c]<br>=0A=<br>> >> =3B END FromChar=3B<br>=0A=<br>> >><br><br>to ensure that all of Text8.New() finishes before the assignment to=<br>> >> fromCharCache[c] is made.<br><br><br>Can the compiler somehow catch these?=<br>> >><br>I fear they are a small epidemic.<br>For a long time people didn't real=<br>> >>ize where all the compiler and processor could reorder.<br><br><br>Do we ha=<br>> >>ve the right constructs by now to fix them?<br>I think we do.<br><br><br> -=<br>> >> Jay<br> </div></body><br>> >></html>=<br>> >><br>> >>--_5f23896e-68ee-44da-82dd-311cd8c58979_--<br></div> </div></body>
</html>