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) ------------------------------------------------------------------------ $ ./ppcmem -model lwsync_read_block -model coherence_points MP+lwsyncs+atomic.litmus ... Test MP+lwsyncs+atomic Allowed States 9 1:r1=0; 2:r1=0; 2:r3=0; 1:r1=0; 2:r1=0; 2:r3=1; 1:r1=0; 2:r1=1; 2:r3=1; 1:r1=0; 2:r1=2; 2:r3=0; 1:r1=0; 2:r1=2; 2:r3=1; 1:r1=1; 2:r1=0; 2:r3=0; 1:r1=1; 2:r1=0; 2:r3=1; 1:r1=1; 2:r1=1; 2:r3=1; 1:r1=1; 2:r1=2; 2:r3=1; No (allowed not found) Condition exists (1:r1=1 /\ 2:r1=2 /\ 2:r3=0) Hash=b7cec0e2ecbd1cb68fe500d6fe362f9c Observation MP+lwsyncs+atomic Never 0 9
