Received-SPF: pass (google.com: domain of linux-kernel+bounces-171502-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1;
From: Puranjay Mohan <puranjay@kernel.org>
To: Andrea Parri <parri.andrea@gmail.com>, Daniel Lustig <dlustig@nvidia.com>
Cc: Will Deacon <will@kernel.org>, Peter Zijlstra <peterz@infradead.org>,
 Boqun Feng <boqun.feng@gmail.com>, Mark Rutland <mark.rutland@arm.com>,
 Paul Walmsley <paul.walmsley@sifive.com>, Palmer Dabbelt
 <palmer@dabbelt.com>, Albert Ou <aou@eecs.berkeley.edu>,
 linux-kernel@vger.kernel.org, linux-riscv@lists.infradead.org
Subject: Re: [PATCH] riscv/atomic.h: optimize ops with acquire/release ordering
In-Reply-To: <ZjgLAKlWC2HQzWfU@andrea>
References: <20240505123340.38495-1-puranjay@kernel.org>
 <ZjgLAKlWC2HQzWfU@andrea>
Date: Tue, 07 May 2024 14:07:26 +0000
Message-ID: <mb61p4jb91zs1.fsf@kernel.org>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Andrea Parri <parri.andrea@gmail.com> writes:

> Hi Puranjay,
>
> On Sun, May 05, 2024 at 12:33:40PM +0000, Puranjay Mohan wrote:
>> Currently, atomic ops with acquire or release ordering are implemented
>> as atomic ops with relaxed ordering followed by or preceded by an
>> acquire fence or a release fence.
>>=20
>> Section 8.1 of the "The RISC-V Instruction Set Manual Volume I:
>> Unprivileged ISA", titled, "Specifying Ordering of Atomic Instructions"
>> says:
>>=20
>> | To provide more efficient support for release consistency [5], each
>> | atomic instruction has two bits, aq and rl, used to specify additional
>> | memory ordering constraints as viewed by other RISC-V harts.
>>=20
>> and
>>=20
>> | If only the aq bit is set, the atomic memory operation is treated as
>> | an acquire access.
>> | If only the rl bit is set, the atomic memory operation is treated as a
>> | release access.
>>=20
>> So, rather than using two instructions (relaxed atomic op + fence), use
>> a single atomic op instruction with acquire/release ordering.
>>=20
>> Example program:
>>=20
>>   atomic_t cnt =3D ATOMIC_INIT(0);
>>   atomic_fetch_add_acquire(1, &cnt);
>>   atomic_fetch_add_release(1, &cnt);
>>=20
>> Before:
>>=20
>>   amoadd.w        a4,a5,(a4)  // Atomic add with relaxed ordering
>>   fence   r,rw                // Fence to force Acquire ordering
>>=20
>>   fence   rw,w                // Fence to force Release ordering
>>   amoadd.w        a4,a5,(a4)  // Atomic add with relaxed ordering
>>=20
>> After:
>>=20
>>   amoadd.w.aq     a4,a5,(a4)  // Atomic add with Acquire ordering
>>=20
>>   amoadd.w.rl     a4,a5,(a4)  // Atomic add with Release ordering
>>=20
>> Signed-off-by: Puranjay Mohan <puranjay@kernel.org>
>
> Your changes are effectively partially reverting:
>
>   5ce6c1f3535fa ("riscv/atomic: Strengthen implementations with fences")
>
> Can you please provide (and possibly include in the changelog of v2) a mo=
re
> thoughtful explanation for the correctness of such revert?
>
> (Anticipating a somewhat non-trivial analysis...)

Hi Andrea,

I think Guo Ren sent a patch[1] like this earlier but it did not get
comments yet. I will reply on that thread[1] as well.

I saw the commit 5ce6c1f3535fa ("riscv/atomic: Strengthen
implementations with fences") and all the related discussions.

This is what I understand from the discussions:

RISCV's LR.aq/SC.rl were following RCpc ordering but the LKMM expected
RCsc ordering from lock() and unlock(). So you added fences to force RCsc
ordering in the locks/atomics.

An experiment with LKMM and RISCV MM:

The following litmus test should not reach (1:r0=3D1 /\ 1:r1=3D0) with LKMM:

C unlock-lock-read-ordering

{}
/* s initially owned by P1 */

P0(int *x, int *y)
{
        WRITE_ONCE(*x, 1);
        smp_wmb();
        WRITE_ONCE(*y, 1);
}

P1(int *x, int *y, spinlock_t *s)
{
        int r0;
        int r1;

        r0 =3D READ_ONCE(*y);
        spin_unlock(s);
        spin_lock(s);
        r1 =3D READ_ONCE(*x);
}

exists (1:r0=3D1 /\ 1:r1=3D0)

Which is indeed true:

Test unlock-lock-read-ordering Allowed
States 3
1:r0=3D0; 1:r1=3D0;
1:r0=3D0; 1:r1=3D1;
1:r0=3D1; 1:r1=3D1;
No
Witnesses
Positive: 0 Negative: 3
Flag unmatched-unlock
Condition exists (1:r0=3D1 /\ 1:r1=3D0)
Observation unlock-lock-read-ordering Never 0 3
Time unlock-lock-read-ordering 0.01
Hash=3Dab0cfdcde54d1bb1faa731533980f424

And when I map this test to RISC-V:

RISCV RISCV-unlock-lock-read-ordering
{
0:x2=3Dx;
0:x4=3Dy;

1:x2=3Dx;
1:x4=3Dy;
1:x6=3Ds;
}
 P0           |  P1                      ;
 ori x1,x0,1  | lw x1,0(x4)              ;
 sw x1,0(x2)  | amoswap.w.rl x0,x0,(x6)  ;
 fence w,w    | ori x5,x0,1              ;
 ori x3,x0,1  | amoswap.w.aq x0,x5,(x6)  ;
 sw x3,0(x4)  | lw x3,0(x2)              ;
exists (1:x1=3D1 /\ 1:x3=3D0)

This also doesn't reach the condition:

Test RISCV-unlock-lock-read-ordering Allowed
States 3
1:x1=3D0; 1:x3=3D0;
1:x1=3D0; 1:x3=3D1;
1:x1=3D1; 1:x3=3D1;
No
Witnesses
Positive: 0 Negative: 3
Condition exists (1:x1=3D1 /\ 1:x3=3D0)
Observation RISCV-unlock-lock-read-ordering Never 0 3
Time RISCV-unlock-lock-read-ordering 0.01
Hash=3Dd845d36e2a8480165903870d135dd81e

Your commit mentioned that the above test would reach the exists
condition for RISCV.

So, maybe the model has been modified to make .aq and .rl RCsc now?

This presentation[2] by Dan Lustig says on page 31:

 | PPO RULES 5-7
 | A release that precedes an acquire in program
 | order also precedes it in global memory order
 | =E2=80=A2 i.e., the RCsc variant of release consistency

If above is true, removing the weak fences and using LR, SC, AMOs with
aq, rl, and aqrl bits could be used in the kernel AMOs and locks.

[1] https://lore.kernel.org/all/20220420144417.2453958-3-guoren@kernel.org/
[2] https://riscv.org/wp-content/uploads/2018/05/14.25-15.00-RISCVMemoryMod=
elTutorial.pdf

Thanks,
Puranjay