[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> =3B VAR buf: ARRAY [0..0] OF CHAR=3B<br> =3B BEGIN<br>=
> >> =3B =3B =3B IF fromCharCache [c] =3D NIL THEN<br> =3B =
> >>=3B =3B =3B =3B buf [0] :=3D c=3B<br> =3B =3B =3B&n=
> >>bsp=3B =3B fromCharCache[c] :=3D Text8.New (buf)=3B<br> =3B =3B=
> >> =3B END=3B<br> =3B =3B =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=
> >> =3B VAR buf: ARRAY [0..0] OF CHAR=3B<br>=0A=
> >> =3B BEGIN<br>=0A=
> >> =3B =3B =3B IF fromCharCache [c] =3D NIL THEN<br>=0A=
> >> =3B =3B =3B =3B =3B buf [0] :=3D c=3B<br>=0A=
> >> =3B =3B =3B =3B =3B WITH a =3D Text8.New (buf) DO<br>&=
> >>nbsp=3B =3B =3B =3B =3B =3B =3B MemoryBarrier()=3B<=
> >>br> =3B =3B =3B =3B =3B =3B =3B fromCharCache[c=
> >>] :=3D a=3B<br> =3B =3B =3B =3B END=3B<br>=0A=
> >> =3B =3B =3B END=3B<br>=0A=
> >> =3B =3B =3B RETURN fromCharCache [c]<br>=0A=
> >> =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