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

Mika Nystrom mika at async.caltech.edu
Mon Aug 27 06:23:51 CEST 2012


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



More information about the M3devel mailing list