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

From: Dan Lustig
Date: Tue Sep 13 2022 - 08:21:20 EST


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