<div dir="ltr">hrmmmm I have a crazy idea<div><br></div><div>"<span style="font-size:9pt;font-family:NeoSansIntel">Compare RAX with </span><span style="font-size:9pt;font-family:'NeoSansIntel,Italic'">r/m64</span><span style="font-size:9pt;font-family:NeoSansIntel">. If equal, ZF is set
and </span><span style="font-size:9pt;font-family:'NeoSansIntel,Italic'">r64 </span><span style="font-size:9pt;font-family:NeoSansIntel">is loaded into </span><span style="font-size:9pt;font-family:'NeoSansIntel,Italic'">r/m64</span><span style="font-size:9pt;font-family:NeoSansIntel">. Else, clear ZF</span></div>
<div><span style="font-size:9pt;font-family:NeoSansIntel">and load </span><span style="font-size:9pt;font-family:'NeoSansIntel,Italic'">r/m64 </span><span style="font-size:9pt;font-family:NeoSansIntel">into RAX.</span>" is what the docs say for the cmpxchng instruction</div>
<div><br></div><div style>so RAX is the old values, (EAX in the 32bit case). And it looks like we dont' set that explicitly when calling the asm .. <span style="font-size:9pt;font-family:NeoSansIntel">CMPXCHG </span><span style="font-size:9pt;font-family:'NeoSansIntel,Italic'">r/m64, r64</span></div>
<div class="" title="Page 605">
<div class="">
<div class="">
<div class="">
<p style><span style="font-size:9pt;font-family:'NeoSansIntel,Italic'"> hrmmm<br></span></p>
</div>
</div>
</div>
</div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Feb 1, 2014 at 12:52 PM, Ryan Newton <span dir="ltr"><<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Ok, here's another experiment, on this commit:<div><br></div><div> <a href="https://github.com/rrnewton/haskell-lockfree/commit/399bb19fa02eaf2f2eab5d02c4b608535362f9bc" target="_blank">https://github.com/rrnewton/haskell-lockfree/commit/399bb19fa02eaf2f2eab5d02c4b608535362f9bc</a><br>
</div><div><br></div><div>Here, if I use GCC's __sync_val_compare_and_swap instead of GHC's version of cas(), the problem also goes away. I think these two implementations should behave identically, and that they don't perhaps indicates that there is something off about the inline asm, as Carter was suggesting:</div>
<div><br></div><div><div><font face="courier new, monospace" size="1"><b>#if i386_HOST_ARCH || x86_64_HOST_ARCH</b></font></div><div><font face="courier new, monospace" size="1"><b> __asm__ __volatile__ (</b></font></div>
<div><font face="courier new, monospace" size="1"><b> <span style="white-space:pre-wrap"> </span> "lock\ncmpxchg %3,%1"</b></font></div><div><font face="courier new, monospace" size="1"><b> :"=a"(o), "=m" (*(volatile unsigned int *)p) </b></font></div>
<div><font face="courier new, monospace" size="1"><b> :"0" (o), "r" (n));</b></font></div><div><font face="courier new, monospace" size="1"><b> return o;</b></font></div></div><div><br></div>
<div>The x86 CAS instruction must put the "return value" in the accumulator register, and indeed this constrains "o" to be allocated to the accumulator register, while the new value "n" can be in any register.</div>
<div><br></div><div>So if there's a problem, I don't know what it is. Except I'm not sure what the ramifications of "o" being a function parameter AND having an "=a" constraint on it are...</div>
<span class="HOEnZb"><font color="#888888">
<div><br></div><div> -Ryan</div><div><br></div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Feb 1, 2014 at 11:27 AM, Carter Schonwald <span dir="ltr"><<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hey Ryan, i've made the leap to using 7.8 on my machine, so i'll first have to get some pull requests in on atomic-primops before I can test it locally :), expect those patches later today!<div>
<br></div>
<div>looks like gcc's inline ASM logic is pretty correct, after testing it a bit locally, pardon my speculative jumping the gun.</div></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Sat, Feb 1, 2014 at 9:10 AM, Ryan Newton <span dir="ltr"><<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Carter & others,<div><br></div><div>Carter, yes, this is CAS on pointers and in my next mail I'll try to come up with some hypotheses as to why we may have (remaining) problems there.</div>
<div><br>
</div><div>But first, I have been assured that on x86 there is no failure mode in which doing a comparison on the value read by CAS should not correctly diagnose success or failure (same as directly reading the Zero Flag) [1]. </div>
<div><br></div><div>And yet, there's this discrepancy, where the modified casMutVar that I linked to does not have the failure. As for reproducing the failure, either of the two following tests will currently show problems:</div>
<div><ul><li>Two threads try to casIORef False->True, both succeed</li><li>120 threads try to read, increment, CAS until they succeed. The total is often not 120 because multiple threads think the successfully incremented, say, 33->34.</li>
</ul></div><div>Here's a specific recipe for the latter test on GHC 7.6.3 Mac or Linux:</div><div><br></div><div><font face="courier new, monospace" size="1"><b>git clone git@github.com:rrnewton/haskell-lockfree-queue.git<br>
</b></font></div><div><font face="courier new, monospace" size="1"><b>cd haskell-lockfree-queue/AtomicPrimops/</b></font></div><div><font face="courier new, monospace" size="1"><b>git checkout 1a1e7e55f6706f9e5754<br></b></font></div>
<div><font face="courier new, monospace" size="1"><b>cabal sandbox init<br></b></font></div><div><font face="courier new, monospace" size="1"><b>cabal install -f-withTH -fforeign ./ ./testing --enable-tests<br></b></font></div>
<div><font face="courier new, monospace" size="1"><b>./testing/dist/dist-sandbox-*/build/test-atomic-primops/test-atomic-primops -t n_threads<br></b></font></div><div><br></div><div>You may have to run the last line several times to see the failure.</div>
<div><br></div><div>Best,</div><div> -Ryan</div><div><br></div><div>[1] I guess the __sync_bool_compare_and_swap intrinsic which reads ZF is there just to avoid the extra comparison.</div><div><br></div><div>[2] P.S. I'd like to try this on GHC head, but the RHEL 6 machine I usually use to build it is currently not validating (below error, commit 65d05d7334). After I debug this gmp problem I'll confirm that the bug under discussion applies on the 7.8 branch.</div>
<div><br></div><div> ./sync-all checkout ghc-7.8</div><div> sh validate</div><div>...</div><div><div>/usr/bin/ld: libraries/integer-gmp/gmp/objs/aors.o: relocation R_X86_64_32 against `__gmpz_sub' can not be used when making a shared object; recompile with -fPIC</div>
<div>libraries/integer-gmp/gmp/objs/aors.o: could not read symbols: Bad value</div></div><div><br></div><div><br></div></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Feb 1, 2014 at 2:55 AM, Carter Schonwald <span dir="ltr"><<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Ryan, is your benchmark using CAS on pointers, or immediate words? trying to get atomic primops to build on my 7.8 build on my mac</div>
<div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Feb 1, 2014 at 2:44 AM, Carter Schonwald <span dir="ltr"><<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><a href="https://ghc.haskell.org/trac/ghc/ticket/8724#ticket" target="_blank">https://ghc.haskell.org/trac/ghc/ticket/8724#ticket</a> is the ticket<br>
<div><br></div><div>when i'm more awake i'll experiment some more</div>
</div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Feb 1, 2014 at 2:33 AM, Carter Schonwald <span dir="ltr"><<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">i have a ticket for tracking this, though i'm thinking my initial attempt at a patch generates the same object code as it did before.<div>
<br></div><div>@ryan, what CPU variant are you testing this on? is this on a NUMA machine or something?</div>
</div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Feb 1, 2014 at 1:58 AM, Carter Schonwald <span dir="ltr"><<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">woops, i mean cmpxchgq</div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Sat, Feb 1, 2014 at 1:36 AM, Carter Schonwald <span dir="ltr"><<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">ok, i can confirm that on my 64bit mac, both clang and gcc use cmpxchgl rather than cmpxchg<div>i'll whip up a strawman patch on head that can be cherrypicked / tested out by ryan et al</div>
</div><div><div>
<div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Feb 1, 2014 at 1:12 AM, Carter Schonwald <span dir="ltr"><<a href="mailto:carter.schonwald@gmail.com" target="_blank">carter.schonwald@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hey Ryan,<div>looking at this closely<br><div>Why isn't CAS using CMPXCHG8B on 64bit architectures? Could that be the culprit? <br>
</div></div><div><br></div><div>Could the issue be that we've not had a good stress test that would create values that are equal on the 32bit range, but differ on the 64bit range, and you're hitting that?</div>
<div><br></div><div>Could you try seeing if doing that change fixes things up?</div><div>(I may be completely wrong, but just throwing this out as a naive "obvious" guess)</div></div><div class="gmail_extra">
<br><br><div class="gmail_quote"><div><div>On Sat, Feb 1, 2014 at 12:58 AM, Ryan Newton <span dir="ltr"><<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>></span> wrote:<br></div>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div>
<div dir="ltr">Then again... I'm having trouble seeing how the spec on page 3-149 of the Intel manual would allow the behavior I'm seeing:<div><br></div><div><a href="http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-manual-325462.pdf" target="_blank">http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-manual-325462.pdf</a><br>
</div><div><br></div><div>Nevertheless, this is exactly the behavior we're seeing with the current Haskell primops. Two threads simultaneously performing the same CAS(p,a,b) can both think that they succeeded.</div>
<div>
<br></div><div><br></div><div><br></div></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Feb 1, 2014 at 12:33 AM, Ryan Newton <span dir="ltr"><<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>I commented on the commit here:</div><div><br></div><div> <a href="https://github.com/ghc/ghc/commit/521b792553bacbdb0eec138b150ab0626ea6f36b" target="_blank">https://github.com/ghc/ghc/commit/521b792553bacbdb0eec138b150ab0626ea6f36b</a><br>
</div><div><br></div><div>The problem is that our "cas" routine in SMP.h is similar to the C compiler intrinsic __sync_val_compare_and_swap, in that it returns the old value. But it seems we cannot use a comparison against that old value to determine whether or not the CAS succeeded. (I believe the CAS may fail due to contention, but the old value may happen to look like our old value.)</div>
<div><br></div><div>Unfortunately, this didn't occur to me until it started causing bugs [1] [2]. Fixing casMutVar# fixes these bugs. However, the way I'm currently fixing CAS in the "atomic-primops" package is by using __sync_bool_compare_and_swap:</div>
<div><br></div> <a href="https://github.com/rrnewton/haskell-lockfree/commit/f9716ddd94d5eff7420256de22cbf38c02322d7a#diff-be3304b3ecdd8e1f9ed316cd844d711aR200" target="_blank">https://github.com/rrnewton/haskell-lockfree/commit/f9716ddd94d5eff7420256de22cbf38c02322d7a#diff-be3304b3ecdd8e1f9ed316cd844d711aR200</a><br>
<div><br></div><div>What is the best fix for GHC itself? Would it be ok for GHC to include a C compiler intrinsic like __sync_val_compare_and_swap? Otherwise we need another big ifdbef'd function like "cas" in SMP.h that has the architecture-specific inline asm across all architectures. I can write the x86 one, but I'm not eager to try the others.</div>
<div><br></div><div>Best,</div><div> -Ryan</div><div><br></div><div>[1] <a href="https://github.com/iu-parfunc/lvars/issues/70" target="_blank">https://github.com/iu-parfunc/lvars/issues/70</a></div><div>[2] <a href="https://github.com/rrnewton/haskell-lockfree/issues/15" target="_blank">https://github.com/rrnewton/haskell-lockfree/issues/15</a></div>
<div><br></div></div>
</blockquote></div><br></div>
</div></div><br></div></div>_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/ghc-devs" target="_blank">http://www.haskell.org/mailman/listinfo/ghc-devs</a><br>
<br></blockquote></div><br></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>