On 9/13/2022 7:24 AM, Will Deacon wrote: > On Fri, Aug 26, 2022 at 01:42:19PM -0700, Paul E. McKenney wrote: >> On Fri, Aug 26, 2022 at 01:10:39PM -0400, Alan Stern wrote: >>> On Fri, Aug 26, 2022 at 06:23:24PM +0200, Peter Zijlstra wrote: >>>> On Fri, Aug 26, 2022 at 05:48:12AM -0700, Paul E. McKenney wrote: >>>>> Hello! >>>>> >>>>> I have not yet done more than glance at this one, but figured I should >>>>> send it along sooner rather than later. >>>>> >>>>> "Verifying and Optimizing Compact NUMA-Aware Locks on Weak >>>>> Memory Models", Antonio Paolillo, Hernán Ponce-de-León, Thomas >>>>> Haas, Diogo Behrens, Rafael Chehab, Ming Fu, and Roland Meyer. >>>>> https://arxiv.org/abs/2111.15240 >>>>> >>>>> The claim is that the queued spinlocks implementation with CNA violates >>>>> LKMM but actually works on all architectures having a formal hardware >>>>> memory model. >>>>> >>>>> Thoughts? >>>> >>>> So the paper mentions the following defects: >>>> >>>> - LKMM doesn't carry a release-acquire chain across a relaxed op >>> >>> That's right, although I'm not so sure this should be considered a >>> defect... >>> >>>> - some babbling about a missing propagation -- ISTR Linux if stuffed >>>> full of them, specifically we require stores to auto propagate >>>> without help from barriers >>> >>> Not a missing propagation; a late one. >>> >>> Don't understand what you mean by "auto propagate without help from >>> barriers". >>> >>>> - some handoff that is CNA specific and I've not looked too hard at >>>> presently. >>>> >>>> >>>> I think we should address that first one in LKMM, it seems very weird to >>>> me a RmW would break the chain like that. >>> >>> An explicitly relaxed RMW (atomic_cmpxchg_relaxed(), to be precise). >>> >>> If the authors wanted to keep the release-acquire chain intact, why not >>> use a cmpxchg version that has release semantics instead of going out of >>> their way to use a relaxed version? >>> >>> To put it another way, RMW accesses and release-acquire accesses are >>> unrelated concepts. You can have one without the other (in principle, >>> anyway). So a relaxed RMW is just as capable of breaking a >>> release-acquire chain as any other relaxed operation is. >>> >>>> Is there actual hardware that >>>> doesn't behave? >>> >>> Not as far as I know, although that isn't very far. Certainly an >>> other-multicopy-atomic architecture would make the litmus test succeed. >>> But the LKMM does not require other-multicopy-atomicity. >> >> My first attempt with ppcmem suggests that powerpc does -not- behave >> this way. But that surprises me, just on general principles. Most likely >> I blew the litmus test shown below. >> >> Thoughts? >> >> Thanx, Paul >> >> ------------------------------------------------------------------------ >> >> PPC MP+lwsyncs+atomic >> "LwSyncdWW Rfe LwSyncdRR Fre" >> Cycle=Rfe LwSyncdRR Fre LwSyncdWW >> { >> 0:r2=x; 0:r4=y; >> 1:r2=y; 1:r5=2; >> 2:r2=y; 2:r4=x; >> } >> P0 | P1 | P2 ; >> li r1,1 | lwarx r1,r0,r2 | lwz r1,0(r2) ; >> stw r1,0(r2) | stwcx. r5,r0,r2 | lwsync ; >> lwsync | | lwz r3,0(r4) ; >> li r3,1 | | ; >> stw r3,0(r4) | | ; >> exists (1:r1=1 /\ 2:r1=2 /\ 2:r3=0) > > Just catching up on this, but one possible gotcha here is if you have an > architecture with native load-acquire on P2 and then you move P2 to the end > of P1. e.g. at a high-level: > > > P0 P1 > Wx = 1 RmW(y) // xchg() 1 => 2 > WyRel = 1 RyAcq = 2 > Rx = 0 > > arm64 forbids this, but it's not "natural" to the hardware and I don't > know what e.g. risc-v would say about it. > > Will RISC-V doesn't currently have native load-acquire instructions other than load-reserve-acquire, but if it did, it would forbid this outcome as well. To the broader question, RISC-V is other-multi-copy-atomic, so questions about propagation order and B-cumulativity and so on aren't generally problematic, just like they generally aren't an issue for ARMv8. Dan
