[M3devel] race conditions in lock-free code...

Jay K jay.krell at cornell.edu
Mon Aug 27 08:27:48 CEST 2012


The processor can reorder. Across call/ret at least in general.


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.)


 - Jay


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


More information about the M3devel mailing list