Re: "Verifying and Optimizing Compact NUMA-Aware Locks on Weak Memory Models"

[Paul E. McKenney]

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