[M3devel] race conditions in lock-free code...
Mika Nystrom
mika at async.caltech.edu
Mon Aug 27 09:17:44 CEST 2012
Oh I see now.
It's not that the processor reorders in any tricky way. It is that the
write performed by Text8.New could be sitting around processor 1's cache
indefinitely without actually getting written back to main memory.
Processor 2 might see the new pointer, but when reading the memory pointed
to, would get uninitialized memory. I think this can happen on Alpha but
maybe not X86 (without further reorderings anyhow)?
Any chance any of the pthreads bugs could be of this nature? How are the
pthreads doing? I gathered some bugs were fixed but I haven't tried the
system for a while.
Mika
Jay K writes:
>--_86f22d85-5540-4565-bf73-232aaafdc94b_
>Content-Type: text/plain; charset="iso-8859-1"
>Content-Transfer-Encoding: quoted-printable
>
>The processor can reorder. Across call/ret at least in general.
>
>
>The compiler can also reorder=2C if you have whole-program-optimization=2C =
>link-time-code-gen (Microsoft "LTCG")=2C link-time-optimization (gcc "LTO")=
>. (We don't=2C but real world systems certainly do.)
>
>
> - Jay
>
>
>> To: jay.krell at cornell.edu=3B m3devel at elegosoft.com=3B mika at async.caltech.=
>edu
>> Subject: Re: [M3devel] race conditions in lock-free code...
>> Date: Sun=2C 26 Aug 2012 22:32:48 -0700
>> From: mika at async.caltech.edu
>>=20
>> Sorry=2C I can't seem to quote your message.
>>=20
>> 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...
>>=20
>> If Text8.New took fromCharCache[c] as a VAR parameter you might be
>> right=2C though. But it doesn't...
>>=20
>> Am I missing something?
>>=20
>> Mika
>>=20
>> Mika Nystrom writes:
>> >
>> >Yeah it's a race condition=2C in theory. But is it important? If you g=
>et
>> >the wrong copy=2C 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=3B charset=3D"iso-8859-1"
>> >>Content-Transfer-Encoding: quoted-printable
>> >>
>> >>We have race conditions=3D2C like this=3D2C m3core/src/Text.m3:
>> >>
>> >>
>> >>VAR fromCharCache :=3D3D ARRAY CHAR OF T {NIL=3D2C ..}=3D3B (* 1-char t=
>exts *)
>> >>
>> >>
>> >>PROCEDURE FromChar (c: CHAR): T =3D3D
>> >> VAR buf: ARRAY [0..0] OF CHAR=3D3B
>> >> BEGIN
>> >> IF fromCharCache [c] =3D3D NIL THEN
>> >> buf [0] :=3D3D c=3D3B
>> >> fromCharCache[c] :=3D3D Text8.New (buf)=3D3B
>> >> END=3D3B
>> >> RETURN fromCharCache [c]
>> >> END FromChar=3D3B
>> >>
>> >>
>> >>It should be:
>> >>
>> >>
>> >>PROCEDURE FromChar (c: CHAR): T =3D3D
>> >>=3D0A=3D
>> >> VAR buf: ARRAY [0..0] OF CHAR=3D3B
>> >>=3D0A=3D
>> >> BEGIN
>> >>=3D0A=3D
>> >> IF fromCharCache [c] =3D3D NIL THEN
>> >>=3D0A=3D
>> >> buf [0] :=3D3D c=3D3B
>> >>=3D0A=3D
>> >> WITH a =3D3D Text8.New (buf) DO
>> >> MemoryBarrier()=3D3B
>> >> fromCharCache[c] :=3D3D a=3D3B
>> >> END=3D3B
>> >>=3D0A=3D
>> >> END=3D3B
>> >>=3D0A=3D
>> >> RETURN fromCharCache [c]
>> >>=3D0A=3D
>> >> END FromChar=3D3B
>> >>=3D0A=3D
>> >>
>> >>
>> >>to ensure that all of Text8.New() finishes before the assignment to fro=
>mCha=3D
>> >>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 proces=
>sor =3D
>> >>could reorder.
>> >>
>> >>
>> >>Do we have the right constructs by now to fix them?
>> >>I think we do.
>> >>
>> >>
>> >> - Jay
>> >> =3D
>> >>
>> >>--_5f23896e-68ee-44da-82dd-311cd8c58979_
>> >>Content-Type: text/html=3B charset=3D"iso-8859-1"
>> >>Content-Transfer-Encoding: quoted-printable
>> >>
>> >><html>
>> >><head>
>> >><style><!--
>> >>.hmmessage P
>> >>{
>> >>margin:0px=3D3B
>> >>padding:0px
>> >>}
>> >>body.hmmessage
>> >>{
>> >>font-size: 12pt=3D3B
>> >>font-family:Calibri
>> >>}
>> >>--></style></head>
>> >><body class=3D3D'hmmessage'><div dir=3D3D'ltr'>We have race conditions=
>=3D2C like =3D
>> >>this=3D2C m3core/src/Text.m3:<br><br><br>VAR fromCharCache :=3D3D ARRAY=
> CHAR OF=3D
>> >> T {NIL=3D2C ..}=3D3B (* 1-char texts *)<br><br><br>PROCEDURE FromChar =
>(c: CHAR=3D
>> >>): T =3D3D<br> =3D3B VAR buf: ARRAY [0..0] OF CHAR=3D3B<br> =3D=
>3B BEGIN<br>=3D
>> >> =3D3B =3D3B =3D3B IF fromCharCache [c] =3D3D NIL THEN<br>&=
>nbsp=3D3B =3D
>> >>=3D3B =3D3B =3D3B =3D3B buf [0] :=3D3D c=3D3B<br> =3D3B=
> =3D3B =3D3B&n=3D
>> >>bsp=3D3B =3D3B fromCharCache[c] :=3D3D Text8.New (buf)=3D3B<br>&nbs=
>p=3D3B =3D3B=3D
>> >> =3D3B END=3D3B<br> =3D3B =3D3B =3D3B RETURN fromCharCa=
>che [c]<br>&nb=3D
>> >>sp=3D3B END FromChar=3D3B<br><br><br>It should be:<br><br><br>PROCEDURE=
> FromCha=3D
>> >>r (c: CHAR): T =3D3D<br>=3D0A=3D
>> >> =3D3B VAR buf: ARRAY [0..0] OF CHAR=3D3B<br>=3D0A=3D
>> >> =3D3B BEGIN<br>=3D0A=3D
>> >> =3D3B =3D3B =3D3B IF fromCharCache [c] =3D3D NIL THEN<br>=
>=3D0A=3D
>> >> =3D3B =3D3B =3D3B =3D3B =3D3B buf [0] :=3D3D c=3D3=
>B<br>=3D0A=3D
>> >> =3D3B =3D3B =3D3B =3D3B =3D3B WITH a =3D3D Text8.N=
>ew (buf) DO<br>&=3D
>> >>nbsp=3D3B =3D3B =3D3B =3D3B =3D3B =3D3B =3D3B M=
>emoryBarrier()=3D3B<=3D
>> >>br> =3D3B =3D3B =3D3B =3D3B =3D3B =3D3B =3D=
>3B fromCharCache[c=3D
>> >>] :=3D3D a=3D3B<br> =3D3B =3D3B =3D3B =3D3B END=3D3B<br=
>>=3D0A=3D
>> >> =3D3B =3D3B =3D3B END=3D3B<br>=3D0A=3D
>> >> =3D3B =3D3B =3D3B RETURN fromCharCache [c]<br>=3D0A=3D
>> >> =3D3B END FromChar=3D3B<br>=3D0A=3D
>> >><br><br>to ensure that all of Text8.New() finishes before the assignmen=
>t to=3D
>> >> fromCharCache[c] is made.<br><br><br>Can the compiler somehow catch th=
>ese?=3D
>> >><br>I fear they are a small epidemic.<br>For a long time people didn't =
>real=3D
>> >>ize where all the compiler and processor could reorder.<br><br><br>Do w=
>e ha=3D
>> >>ve the right constructs by now to fix them?<br>I think we do.<br><br><b=
>r> -=3D
>> >> Jay<br> </div></body>
>> >></html>=3D
>> >>
>> >>--_5f23896e-68ee-44da-82dd-311cd8c58979_--
> =
>
>--_86f22d85-5540-4565-bf73-232aaafdc94b_
>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'>The processor can reorder. Acros=
>s call/ret at least in general.<br><br><br>The compiler can also reorder=2C=
> if you have whole-program-optimization=2C link-time-code-gen (Microsoft "L=
>TCG")=2C link-time-optimization (gcc "LTO"). (We don't=2C but real world sy=
>stems certainly do.)<br><br><br> =3B- Jay<br><br><br><div><div id=3D"Sk=
>yDrivePlaceholder"></div>>=3B To: jay.krell at cornell.edu=3B m3devel at elegos=
>oft.com=3B mika at async.caltech.edu<br>>=3B Subject: Re: [M3devel] race con=
>ditions in lock-free code...<br>>=3B Date: Sun=2C 26 Aug 2012 22:32:48 -0=
>700<br>>=3B From: mika at async.caltech.edu<br>>=3B <br>>=3B Sorry=2C I =
>can't seem to quote your message.<br>>=3B <br>>=3B You say that Text8.N=
>ew's result can be assigned to fromCharCache[c]<br>>=3B before Text8.New =
>is done running. How is that possible? Surely<br>>=3B Text8.New has to =
>calculate its result before it can be assigned<br>>=3B anywhere. Yes pos=
>sibly FromChar allocates space for the result of<br>>=3B Text8.New but th=
>e assignment of whatever appears in that space can't<br>>=3B happen until=
> *after* Text8.New has run. Unless you are saying that<br>>=3B the runni=
>ng of Text8.New and FromChar are intertwined somehow..?<br>>=3B I know co=
>mpilers do some odd things but that doesn't sound right...<br>>=3B <br>&g=
>t=3B If Text8.New took fromCharCache[c] as a VAR parameter you might be<br>=
>>=3B right=2C though. But it doesn't...<br>>=3B <br>>=3B Am I missin=
>g something?<br>>=3B <br>>=3B Mika<br>>=3B <br>>=3B Mika Nystr=
>om writes:<br>>=3B >=3B<br>>=3B >=3BYeah it's a race condition=2C i=
>n theory. But is it important? If you get<br>>=3B >=3Bthe wrong copy=
>=2C there will be two TEXTs representing one CHAR. But no<br>>=3B >=3B=
>one ever said FromChar was guaranteed to return the same pointer when<br>&g=
>t=3B >=3Byou call it with the same CHAR...<br>>=3B >=3B<br>>=3B >=
>=3B Mika<br>>=3B >=3B<br>>=3B >=3BJay K writes:<br>>=3B >=
>=3B>=3B--_5f23896e-68ee-44da-82dd-311cd8c58979_<br>>=3B >=3B>=3BCon=
>tent-Type: text/plain=3B charset=3D"iso-8859-1"<br>>=3B >=3B>=3BConte=
>nt-Transfer-Encoding: quoted-printable<br>>=3B >=3B>=3B<br>>=3B >=
>=3B>=3BWe have race conditions=3D2C like this=3D2C m3core/src/Text.m3:<br=
>>>=3B >=3B>=3B<br>>=3B >=3B>=3B<br>>=3B >=3B>=3BVAR fromC=
>harCache :=3D3D ARRAY CHAR OF T {NIL=3D2C ..}=3D3B (* 1-char texts *)<br>&g=
>t=3B >=3B>=3B<br>>=3B >=3B>=3B<br>>=3B >=3B>=3BPROCEDURE Fr=
>omChar (c: CHAR): T =3D3D<br>>=3B >=3B>=3B VAR buf: ARRAY [0..0] OF =
>CHAR=3D3B<br>>=3B >=3B>=3B BEGIN<br>>=3B >=3B>=3B IF fromCh=
>arCache [c] =3D3D NIL THEN<br>>=3B >=3B>=3B buf [0] :=3D3D c=3D3=
>B<br>>=3B >=3B>=3B fromCharCache[c] :=3D3D Text8.New (buf)=3D3B<=
>br>>=3B >=3B>=3B END=3D3B<br>>=3B >=3B>=3B RETURN fromCha=
>rCache [c]<br>>=3B >=3B>=3B END FromChar=3D3B<br>>=3B >=3B>=3B=
><br>>=3B >=3B>=3B<br>>=3B >=3B>=3BIt should be:<br>>=3B >=
>=3B>=3B<br>>=3B >=3B>=3B<br>>=3B >=3B>=3BPROCEDURE FromChar (=
>c: CHAR): T =3D3D<br>>=3B >=3B>=3B=3D0A=3D<br>>=3B >=3B>=3B VA=
>R buf: ARRAY [0..0] OF CHAR=3D3B<br>>=3B >=3B>=3B=3D0A=3D<br>>=3B &=
>gt=3B>=3B BEGIN<br>>=3B >=3B>=3B=3D0A=3D<br>>=3B >=3B>=3B =
> IF fromCharCache [c] =3D3D NIL THEN<br>>=3B >=3B>=3B=3D0A=3D<br>>=
>=3B >=3B>=3B buf [0] :=3D3D c=3D3B<br>>=3B >=3B>=3B=3D0A=3D<=
>br>>=3B >=3B>=3B WITH a =3D3D Text8.New (buf) DO<br>>=3B >=
>=3B>=3B MemoryBarrier()=3D3B<br>>=3B >=3B>=3B fromCha=
>rCache[c] :=3D3D a=3D3B<br>>=3B >=3B>=3B END=3D3B<br>>=3B >=
>=3B>=3B=3D0A=3D<br>>=3B >=3B>=3B END=3D3B<br>>=3B >=3B>=3B=
>=3D0A=3D<br>>=3B >=3B>=3B RETURN fromCharCache [c]<br>>=3B >=
>=3B>=3B=3D0A=3D<br>>=3B >=3B>=3B END FromChar=3D3B<br>>=3B >=
>=3B>=3B=3D0A=3D<br>>=3B >=3B>=3B<br>>=3B >=3B>=3B<br>>=3B &=
>gt=3B>=3Bto ensure that all of Text8.New() finishes before the assignment=
> to fromCha=3D<br>>=3B >=3B>=3BrCache[c] is made.<br>>=3B >=3B>=
>=3B<br>>=3B >=3B>=3B<br>>=3B >=3B>=3BCan the compiler somehow c=
>atch these?<br>>=3B >=3B>=3BI fear they are a small epidemic.<br>>=
>=3B >=3B>=3BFor a long time people didn't realize where all the compile=
>r and processor =3D<br>>=3B >=3B>=3Bcould reorder.<br>>=3B >=3B&g=
>t=3B<br>>=3B >=3B>=3B<br>>=3B >=3B>=3BDo we have the right cons=
>tructs by now to fix them?<br>>=3B >=3B>=3BI think we do.<br>>=3B &=
>gt=3B>=3B<br>>=3B >=3B>=3B<br>>=3B >=3B>=3B - Jay<br>>=3B &=
>gt=3B>=3B =3D<br>>=3B >=3B>=3B<br>>=3B >=3B>=3B--_=
>5f23896e-68ee-44da-82dd-311cd8c58979_<br>>=3B >=3B>=3BContent-Type: t=
>ext/html=3B charset=3D"iso-8859-1"<br>>=3B >=3B>=3BContent-Transfer-E=
>ncoding: quoted-printable<br>>=3B >=3B>=3B<br>>=3B >=3B>=3B<=
>=3Bhtml>=3B<br>>=3B >=3B>=3B<=3Bhead>=3B<br>>=3B >=3B>=3B=
><=3Bstyle>=3B<=3B!--<br>>=3B >=3B>=3B.hmmessage P<br>>=3B >=
>=3B>=3B{<br>>=3B >=3B>=3Bmargin:0px=3D3B<br>>=3B >=3B>=3Bpadd=
>ing:0px<br>>=3B >=3B>=3B}<br>>=3B >=3B>=3Bbody.hmmessage<br>>=
>=3B >=3B>=3B{<br>>=3B >=3B>=3Bfont-size: 12pt=3D3B<br>>=3B >=
>=3B>=3Bfont-family:Calibri<br>>=3B >=3B>=3B}<br>>=3B >=3B>=3B=
>-->=3B<=3B/style>=3B<=3B/head>=3B<br>>=3B >=3B>=3B<=3Bbod=
>y class=3D3D'hmmessage'>=3B<=3Bdiv dir=3D3D'ltr'>=3BWe have race cond=
>itions=3D2C like =3D<br>>=3B >=3B>=3Bthis=3D2C m3core/src/Text.m3:<=
>=3Bbr>=3B<=3Bbr>=3B<=3Bbr>=3BVAR fromCharCache :=3D3D ARRAY CHAR =
>OF=3D<br>>=3B >=3B>=3B T {NIL=3D2C ..}=3D3B (* 1-char texts *)<=3Bb=
>r>=3B<=3Bbr>=3B<=3Bbr>=3BPROCEDURE FromChar (c: CHAR=3D<br>>=3B=
> >=3B>=3B): T =3D3D<=3Bbr>=3B&=3Bnbsp=3D3B VAR buf: ARRAY [0..0]=
> OF CHAR=3D3B<=3Bbr>=3B&=3Bnbsp=3D3B BEGIN<=3Bbr>=3B=3D<br>>=
>=3B >=3B>=3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B IF fromCha=
>rCache [c] =3D3D NIL THEN<=3Bbr>=3B&=3Bnbsp=3D3B&=3Bnbsp=3D<br>&g=
>t=3B >=3B>=3B=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B buf =
>[0] :=3D3D c=3D3B<=3Bbr>=3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=
>=3D3B&=3Bn=3D<br>>=3B >=3B>=3Bbsp=3D3B&=3Bnbsp=3D3B fromCharCac=
>he[c] :=3D3D Text8.New (buf)=3D3B<=3Bbr>=3B&=3Bnbsp=3D3B&=3Bnbsp=
>=3D3B=3D<br>>=3B >=3B>=3B&=3Bnbsp=3D3B END=3D3B<=3Bbr>=3B&=
>=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B RETURN fromCharCache [c]<=3B=
>br>=3B&=3Bnb=3D<br>>=3B >=3B>=3Bsp=3D3B END FromChar=3D3B<=3Bb=
>r>=3B<=3Bbr>=3B<=3Bbr>=3BIt should be:<=3Bbr>=3B<=3Bbr>=
>=3B<=3Bbr>=3BPROCEDURE FromCha=3D<br>>=3B >=3B>=3Br (c: CHAR): T =
>=3D3D<=3Bbr>=3B=3D0A=3D<br>>=3B >=3B>=3B&=3Bnbsp=3D3B VAR buf:=
> ARRAY [0..0] OF CHAR=3D3B<=3Bbr>=3B=3D0A=3D<br>>=3B >=3B>=3B&=
>=3Bnbsp=3D3B BEGIN<=3Bbr>=3B=3D0A=3D<br>>=3B >=3B>=3B&=3Bnbsp=
>=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B IF fromCharCache [c] =3D3D NIL THEN&l=
>t=3Bbr>=3B=3D0A=3D<br>>=3B >=3B>=3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B=
>&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B buf [0] :=3D3D c=3D3B<=
>=3Bbr>=3B=3D0A=3D<br>>=3B >=3B>=3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=
>amp=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B WITH a =3D3D Text8.New (buf=
>) DO<=3Bbr>=3B&=3B=3D<br>>=3B >=3B>=3Bnbsp=3D3B&=3Bnbsp=3D3=
>B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbs=
>p=3D3B MemoryBarrier()=3D3B<=3B=3D<br>>=3B >=3B>=3Bbr>=3B&=3Bn=
>bsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&am=
>p=3Bnbsp=3D3B&=3Bnbsp=3D3B fromCharCache[c=3D<br>>=3B >=3B>=3B] :=
>=3D3D a=3D3B<=3Bbr>=3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=
>amp=3Bnbsp=3D3B END=3D3B<=3Bbr>=3B=3D0A=3D<br>>=3B >=3B>=3B&=
>=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B END=3D3B<=3Bbr>=3B=3D0A=3D=
><br>>=3B >=3B>=3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B&=3Bnbsp=3D3B RET=
>URN fromCharCache [c]<=3Bbr>=3B=3D0A=3D<br>>=3B >=3B>=3B&=3Bnb=
>sp=3D3B END FromChar=3D3B<=3Bbr>=3B=3D0A=3D<br>>=3B >=3B>=3B<=
>=3Bbr>=3B<=3Bbr>=3Bto ensure that all of Text8.New() finishes before =
>the assignment to=3D<br>>=3B >=3B>=3B fromCharCache[c] is made.<=3B=
>br>=3B<=3Bbr>=3B<=3Bbr>=3BCan the compiler somehow catch these?=
>=3D<br>>=3B >=3B>=3B<=3Bbr>=3BI fear they are a small epidemic.&l=
>t=3Bbr>=3BFor a long time people didn't real=3D<br>>=3B >=3B>=3Bize=
> where all the compiler and processor could reorder.<=3Bbr>=3B<=3Bbr&=
>gt=3B<=3Bbr>=3BDo we ha=3D<br>>=3B >=3B>=3Bve the right construct=
>s by now to fix them?<=3Bbr>=3BI think we do.<=3Bbr>=3B<=3Bbr>=
>=3B<=3Bbr>=3B -=3D<br>>=3B >=3B>=3B Jay<=3Bbr>=3B =
><=3B/div>=3B<=3B/body>=3B<br>>=3B >=3B>=3B<=3B/html>=3B=
>=3D<br>>=3B >=3B>=3B<br>>=3B >=3B>=3B--_5f23896e-68ee-44da-82dd=
>-311cd8c58979_--<br></div> </div></body>
></html>=
>
>--_86f22d85-5540-4565-bf73-232aaafdc94b_--
More information about the M3devel
mailing list