Re: [Gc] test_stack on powerpc (power7)
Hans Boehm <[email protected]> Sat, 13 Aug 2016 13:55:16 -0700
| Newsgroups | gmane.comp.programming.garbage-collection.boehmgc |
|---|---|
| Message-ID | <CAPUmR1Yb0NGJeEfuJ_gGSQNisKhaumLoXZZvoxDESVv_yyg_AQ@mail.gmail.com> |
--===============1707730122== Content-Type: multipart/alternative; boundary=94eb2c04a26c66d5d30539fa3774 --94eb2c04a26c66d5d30539fa3774 Content-Type: text/plain; charset=UTF-8 I finally had a chance to look at this. Sorry about the llloooonnnnngggggg delay. This is really a combination of imprecision in the atomic_ops definitions, my lack of understanding of PowerPC semantics at the time, and the resulting sloppiness in the stack implementation. I think that the core issue is that AO_stack_pop_explicit_aux_acquire really needs to ensure that the store to the black list via AO_compare_and_swap_acquire becomes visible before the load to check the list head on line 155. This effectively needs store->load ordering. Currently the only ordering here is imposed by the _acquire on the compare_and_swap. On PowerPC that turns into an lwsync, which is too weak to enforce store to load ordering. Given our current definitions, it's probably best to drop the _acquire from the CAS on line 136, and add a AO_nop_full just before line 154. This is suboptimal on x86, and we may want to make the fence conditional on "not x86", where the CAS already includes sufficient ordering. (With C++11 atomics, this would also be tricky and probably involve making a bunch of accesses seq_cst.) It would be good if someone with PowerPC access could confirm that this fixes the problem. Hans On Wed, Aug 3, 2016 at 1:16 PM, Ivan Maidanski <ivmai-JGs/[email protected]> wrote: > Hello Pavel, > > > I've seen Fedora maintainer applied this workaround downstream. My > question is whether it is better to have it applied, or rather not. > No. I checked gcc (4.8 ppc64le) __atomic_load_n - it is the same as > current AO_load implementation. This means even if we apply this hack and > later switch to gcc atomics then the issue comes again. > > But I'm OK with more local change - replace one or several AO_load > operations with AO_load_acquire in atomic_ops_stack.c for power7 - this is, > of course, still a hack as we don't know the root cause of the failure. > > 1. The attached patch should work but please check it. > 2. Is it possible to make the patch with a smaller number of changes? > > > I need to understand more deeply the "stack_aux" structure and how you > are using it, I still can't see whether there is guaranteed that the > background algorithm may not have collisions (considering 2+ threads trying > to make a pop and 2+ threads trying to make a push operation in parallel). > I want Hans to look at it deeper. (It seems he's busy at this moment.) > > PS. Link to the issue on Github: https://github.com/ivmai/ > libatomic_ops/issues/15 > > Regards, > Ivan > > Wed, 27 Jul 2016, 21:26 +03:00 from Ivan Maidanski <ivmai-JGs/[email protected]>: > > > Hello Pavel and Hans, > > To Pavel: > > I've seen Fedora maintainer applied this workaround downstream. > Please give a reference? (sorry I failed to access the patch in ML) > > To Hans: > What do you think of the failure reason? Could you please better > description of stack_aux? > On Mon, 2012-12-17 at 15:34 +0100, Pavel Raiskup wrote: > > ... > > I need to understand more deeply the "stack_aux" structure and how you > are using it, I still can't see whether there is guaranteed that the > background algorithm may not have collisions (considering 2+ threads trying > to make a pop and 2+ threads trying to make a push operation in parallel). > > Regards, > Ivan > > Wed, 27 Jul 2016, 17:40 +03:00 from Pavel Raiskup <[email protected]>: > > On Sunday, February 16, 2014 7:20:13 PM CEST Ivan Maidanski wrote: > > Hi Will, > > > > I don't think current definition of AO_load is incorrect. (The definition > > has never been changed and all other supported platforms have the same > > no-barrier atomic load definition.) > > > > Probably the barrier should be added to stack implementation. > > Is it really correct to have "first = AO_load(list)" (in > AO_stack_pop_explicit_aux_acquire) instead of "first = > AO_load_acquire(list)" ? > > I've seen Fedora maintainer applied this workaround downstream. My > question is > whether it is better to have it applied, or rather not. > > Note that there were some attempts to make this work on ppc64 before: > http://comments.gmane.org/gmane.comp.programming. > garbage-collection.boehmgc/5470 > > That thread is however scattered across several mailing list archives -> > I've > posted one patch for which I would love to hear ideas: > http://www.hpl.hp.com/hosted/linux/mail-archives/gc/2012- > December/005507.html > > Pavel > _______________________________________________ > bdwgc mailing list > [email protected] > https://lists.opendylan.org/mailman/listinfo/bdwgc > > > > --94eb2c04a26c66d5d30539fa3774 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">I finally had a chance to look at this.=C2=A0 Sorry about = the llloooonnnnngggggg delay.<div><br></div><div>This is really a combinati= on of imprecision in the atomic_ops definitions, my lack of understanding o= f PowerPC semantics at the time, and the resulting sloppiness in the stack = implementation.</div><div><br></div><div>I think that the core issue is tha= t=C2=A0AO_stack_pop_explicit_aux_acquire really needs to ensure that the st= ore to the black list via=C2=A0AO_compare_and_swap_acquire becomes visible = before the load to check the list head on line 155.=C2=A0 This effectively = needs store->load ordering. Currently the only ordering here is imposed = by the _acquire on the compare_and_swap. On PowerPC that turns into an lwsy= nc, which is too weak to enforce store to load ordering.</div><div><br></di= v><div>Given our current definitions, it's probably best to drop the _a= cquire from the CAS on line 136, and add a AO_nop_full just before line 154= .=C2=A0 This is suboptimal on x86, and we may want to make the fence condit= ional on "not x86", where the CAS already includes sufficient ord= ering. =C2=A0(With C++11 atomics, this would also be tricky and probably in= volve making a bunch of accesses seq_cst.)</div><div><br></div><div>It woul= d be good if someone with PowerPC access could confirm that this fixes the = problem.</div><div><br></div><div>Hans</div></div><div class=3D"gmail_extra= "><br><div class=3D"gmail_quote">On Wed, Aug 3, 2016 at 1:16 PM, Ivan Maida= nski <span dir=3D"ltr"><<a href=3D"mailto:ivmai-JGs/[email protected]" target=3D"_blan= k">ivmai-JGs/[email protected]</a>></span> wrote:<br><blockquote class=3D"gmail_quote"= style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div>Hello Pavel,<br><div><br></div><div><span class=3D"">> I've see= n Fedora maintainer applied this workaround downstream. My question is whet= her it is better to have it applied, or rather not.<br></span>No. I checked= gcc (4.8 ppc64le) __atomic_load_n - it is the same as current AO_load impl= ementation. This means even if we apply this hack and later switch to gcc a= tomics then the issue comes again.<br></div><br>But I'm OK with more lo= cal change - replace one or several AO_load operations with AO_load_acquire= in atomic_ops_stack.c for power7 - this is, of course, still a hack as we = don't know the root cause of the failure.<br><br>1. The attached patch = should work but please check it.<br>2. Is it possible to make the patch wit= h a smaller number of changes?<span class=3D""><br><br>> I need to under= stand more deeply the "stack_aux" structure and how you are using= it, I still can't see whether there is guaranteed that the background = algorithm may not have collisions (considering 2+ threads trying to make a = pop and 2+ threads trying to make a push operation in parallel).<br></span>= I want Hans to look at it deeper. (It seems he's busy at this moment.)<= br><br>PS. Link to the issue on Github: <a href=3D"https://github.com/ivmai= /libatomic_ops/issues/15" target=3D"_blank">https://github.com/ivmai/<wbr>l= ibatomic_ops/issues/15</a><br><br>Regards,<br>Ivan<br><br><blockquote style= =3D"border-left:1px solid #0857a6;margin:10px;padding:0 0 0 10px"> Wed, 27 Jul 2016, 21:26 +03:00 from Ivan Maidanski <<a href=3D"mailto:i= vmai-JGs/[email protected]" target=3D"_blank">ivmai-JGs/[email protected]</a>>:<div><div class=3D"h5= "><br> <br> <div> =09 <div> =09 <div> =09 =09 <div> Hello Pavel and Hans,<br><br>To Pavel:<br>> I've seen Fedora maintai= ner applied this workaround downstream.<br>Please give a reference? (sorry = I failed to access the patch in ML)<br><br>To Hans:<br>What do you think of= the failure reason? Could you please better description of stack_aux?<br>O= n Mon, 2012-12-17 at 15:34 +0100, Pavel Raiskup wrote:<br>> ... <br>>= I need to understand more deeply the "stack_aux" structure and h= ow you are using it, I still can't see whether there is guaranteed that= the background algorithm may not have collisions (considering 2+ threads t= rying to make a pop and 2+ threads trying to make a push operation in paral= lel).<br><br>Regards,<br>Ivan<br><br><blockquote style=3D"border-left:1px s= olid #0857a6;margin:10px;padding:0 0 0 10px"> Wed, 27 Jul 2016, 17:40 +03:00 from Pavel Raiskup <<a href=3D"mailto:pr= [email protected]" target=3D"_blank">[email protected]</a>>:<br> <br> <div> =09 <div> =09 <div> =09 =09 <div>On Sunday, February 16, 2014 7:20:13 PM CEST Ivan Maidansk= i wrote:<br> > Hi Will,<br> > <br> > I don't think current definition of AO_load is incorrect. (The def= inition<br> > has never been changed and all other supported platforms have the same= <br> > no-barrier atomic load definition.)<br> > <br> > Probably the barrier should be added to stack implementation.<br> > Is it really correct to have "first =3D AO_load(list)" (in A= O_stack_pop_explicit_aux_<wbr>acquire) instead of "first =3D AO_load_a= cquire(list)" ?<br> <br> I've seen Fedora maintainer applied this workaround downstream. My que= stion is<br> whether it is better to have it applied, or rather not.<br> <br> Note that there were some attempts to make this work on ppc64 before:<br> <a href=3D"http://comments.gmane.org/gmane.comp.programming.garbage-collect= ion.boehmgc/5470" target=3D"_blank">http://comments.gmane.org/<wbr>gmane.co= mp.programming.<wbr>garbage-collection.boehmgc/<wbr>5470</a><br> <br> That thread is however scattered across several mailing list archives ->= I've<br> posted one patch for which I would love to hear ideas:<br> <a href=3D"http://www.hpl.hp.com/hosted/linux/mail-archives/gc/2012-Decembe= r/005507.html" target=3D"_blank">http://www.hpl.hp.com/hosted/<wbr>linux/ma= il-archives/gc/2012-<wbr>December/005507.html</a><br> <br> Pavel<br> ______________________________<wbr>_________________<br> bdwgc mailing list<br> <a href=3D"mailto:[email protected]" target=3D"_blank">bdwgc@lists.= opendylan.org</a><br> <a href=3D"https://lists.opendylan.org/mailman/listinfo/bdwgc" target=3D"_b= lank">https://lists.opendylan.org/<wbr>mailman/listinfo/bdwgc</a><br> </div> =20 =20 =09 </div> =09 </div> </div> </blockquote> <br> </div> =20 =20 =09 </div> =09 </div> </div> </div></div></blockquote> <br></div> </blockquote></div><br></div> --94eb2c04a26c66d5d30539fa3774-- --===============1707730122== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ bdwgc mailing list [email protected] https://lists.opendylan.org/mailman/listinfo/bdwgc --===============1707730122==--