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

Mon Aug 27 07:32:48 CEST 2012

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_--