MIME-Version: 1.0
From: Alexander Korotkov <aekorotkov@gmail.com>
Date: Fri, 7 Mar 2025 17:47:08 +0200
Message-ID: 
 <CAPpHfdudejddHLLw=Uk_7pZ=1g2SZXfwubSgmWUhJ7fBUtR9rg@mail.gmail.com>
Subject: pg_atomic_compare_exchange_*() and memory barriers
To: pgsql-hackers <pgsql-hackers@postgresql.org>
Content-Type: multipart/alternative; boundary="0000000000009e97e7062fc289bf"
Archived-At: 
 <https://www.postgresql.org/message-id/CAPpHfdudejddHLLw%3DUk_7pZ%3D1g2SZXfwubSgmWUhJ7fBUtR9rg%40mail.gmail.com>
Precedence: bulk

--0000000000009e97e7062fc289bf
Content-Type: text/plain; charset="UTF-8"

Hi all,

While investigating a bug in the patch to get rid of WALBufMappingLock, I
found that the surrounding pg_atomic_compare_exchange_u64() fixes the
problem for me.  That doesn't feel right because, according to the
comments, both pg_atomic_compare_exchange_u32() and
pg_atomic_compare_exchange_u64() should provide full memory barrier
semantics.  So, I decided to investigate this further.

In my case, the implementation of pg_atomic_compare_exchange_u64() is based
on __atomic_compare_exchange_n().

static inline bool
pg_atomic_compare_exchange_u64_impl(volatile pg_atomic_uint64 *ptr,
                                    uint64 *expected, uint64 newval)
{
    AssertPointerAlignment(expected, 8);
    return __atomic_compare_exchange_n(&ptr->value, expected, newval, false,
                                       __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
}

According to the docs __ATOMIC_SEQ_CST enforces total ordering with *all
other __ATOMIC_SEQ_CST operations*.  It only says about other
__ATOMIC_SEQ_CST operations; nothing is said about regular reads/writes.
This sounds quite far from our comment, promising full barrier semantics,
which, in my understanding, means the equivalent of
both pg_read_barrier()/pg_write_barrier(), which should barrier *all other
read/writes*.

I've found that __atomic_compare_exchange_n() ends up with usage
of __aarch64_cas8_acq_rel, which disassembles as following.

0000000000000860 <__aarch64_cas8_acq_rel>:
 860:   d503245f    bti c
 864:   90000110    adrp    x16, 20000 <__data_start>
 868:   3940a210    ldrb    w16, [x16, #40]
 86c:   34000070    cbz w16, 878 <__aarch64_cas8_acq_rel+0x18>
 870:   c8e0fc41    casal   x0, x1, [x2]
 874:   d65f03c0    ret
 878:   aa0003f0    mov x16, x0
 87c:   c85ffc40    ldaxr   x0, [x2]
 880:   eb10001f    cmp x0, x16
 884:   54000061    b.ne    890 <__aarch64_cas8_acq_rel+0x30>  // b.any
 888:   c811fc41    stlxr   w17, x1, [x2]
 88c:   35ffff91    cbnz    w17, 87c <__aarch64_cas8_acq_rel+0x1c>
 890:   d65f03c0    ret

This function first checks if LSE instructions are present.  If so,
instruction LSE casal is used.  If not (in my case), the loop of
ldaxr/stlxr is used instead.  The documentation says both ldaxr/stlxr
provides one-way barriers.  Read/writes after ldaxr will be observed after,
and read/writes before stlxr will be observed before.  So, a pair of these
instructions provides a full memory barrier.  However, if we don't observe
the expected value, only ldaxr gets executed.  So, an unsuccessful
pg_atomic_compare_exchange_u64() attempt will leave us with a one-way
barrier, and that caused a bug in my case.  In contrast,
__sync_val_compare_and_swap() uses __aarch64_cas8_sync, which is quite the
same as __aarch64_cas8_acq_rel, but has an explicit memory barrier in the
end.

I have a couple of ideas on how to fix this problem.
1. Provide full barrier semantics for pg_atomic_compare_exchange_*().  In
particular, for __atomic_compare_exchange_n(), we should probably
use __ATOMIC_ACQ_REL for success and run an explicit memory barrier in the
case of failure.
2. Document that pg_atomic_compare_exchange_*() doesn't necessarily provide
a memory barrier on failure.  But then we need to carefully check if
existing use-cases need explicit memory barriers now.

Any thoughts?

Links
1.
https://www.postgresql.org/message-id/CAPpHfdsWcQb-u-9K%3DipneBf8CMhoUuBWKYc%2BXWJEHVdtONOepQ%40mail.gmail.com
2. https://developer.arm.com/documentation/100941/0101/Barriers

------
Regards,
Alexander Korotkov
Supabase

--0000000000009e97e7062fc289bf
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi all,<br><br>While investigating a bug in the patch to g=
et rid of WALBufMappingLock, I found that the surrounding pg_atomic_compare=
_exchange_u64() fixes the problem for me.=C2=A0 That doesn&#39;t feel right=
 because, according to the comments, both pg_atomic_compare_exchange_u32() =
and pg_atomic_compare_exchange_u64() should provide full memory barrier sem=
antics.=C2=A0 So, I decided to investigate this further.<br><br>In my case,=
 the implementation of pg_atomic_compare_exchange_u64() is based on __atomi=
c_compare_exchange_n().<div><br><font face=3D"monospace">static inline bool=
<br>pg_atomic_compare_exchange_u64_impl(volatile pg_atomic_uint64 *ptr,<br>=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 uint64 *expected, uint=
64 newval)<br>{<br>=C2=A0 =C2=A0 AssertPointerAlignment(expected, 8);<br>=
=C2=A0 =C2=A0 return __atomic_compare_exchange_n(&amp;ptr-&gt;value, expect=
ed, newval, false,<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);<br>}<br></font><br>Accord=
ing to the docs=C2=A0__ATOMIC_SEQ_CST enforces total ordering with <b>all o=
ther __ATOMIC_SEQ_CST operations</b>.=C2=A0 It only says about other __ATOM=
IC_SEQ_CST operations; nothing is said about regular reads/writes.=C2=A0 Th=
is sounds quite far from our comment, promising full barrier semantics, whi=
ch, in my understanding, means the equivalent of both=C2=A0pg_read_barrier(=
)/pg_write_barrier(), which should barrier <b>all other read/writes</b>.<di=
v><br></div><div>I&#39;ve found that=C2=A0__atomic_compare_exchange_n() end=
s up with usage of=C2=A0__aarch64_cas8_acq_rel, which disassembles as follo=
wing.</div><div><br></div><div><font face=3D"monospace">0000000000000860 &l=
t;__aarch64_cas8_acq_rel&gt;:<br>=C2=A0860: =C2=A0 d503245f =C2=A0 =C2=A0bt=
i c<br>=C2=A0864: =C2=A0 90000110 =C2=A0 =C2=A0adrp =C2=A0 =C2=A0x16, 20000=
 &lt;__data_start&gt;<br>=C2=A0868: =C2=A0 3940a210 =C2=A0 =C2=A0ldrb =C2=
=A0 =C2=A0w16, [x16, #40]<br>=C2=A086c: =C2=A0 34000070 =C2=A0 =C2=A0cbz w1=
6, 878 &lt;__aarch64_cas8_acq_rel+0x18&gt;<br>=C2=A0870: =C2=A0 c8e0fc41 =
=C2=A0 =C2=A0casal =C2=A0 x0, x1, [x2]<br>=C2=A0874: =C2=A0 d65f03c0 =C2=A0=
 =C2=A0ret<br>=C2=A0878: =C2=A0 aa0003f0 =C2=A0 =C2=A0mov x16, x0<br>=C2=A0=
87c: =C2=A0 c85ffc40 =C2=A0 =C2=A0ldaxr =C2=A0 x0, [x2]<br>=C2=A0880: =C2=
=A0 eb10001f =C2=A0 =C2=A0cmp x0, x16<br>=C2=A0884: =C2=A0 54000061 =C2=A0 =
=C2=A0<a href=3D"http://b.ne">b.ne</a> =C2=A0 =C2=A0890 &lt;__aarch64_cas8_=
acq_rel+0x30&gt; =C2=A0// b.any<br>=C2=A0888: =C2=A0 c811fc41 =C2=A0 =C2=A0=
stlxr =C2=A0 w17, x1, [x2]<br>=C2=A088c: =C2=A0 35ffff91 =C2=A0 =C2=A0cbnz =
=C2=A0 =C2=A0w17, 87c &lt;__aarch64_cas8_acq_rel+0x1c&gt;<br>=C2=A0890: =C2=
=A0 d65f03c0 =C2=A0 =C2=A0ret</font></div><div><br></div>This function firs=
t checks if LSE instructions are present.=C2=A0 If so, instruction LSE casa=
l is used.=C2=A0 If not (in my case), the loop of ldaxr/stlxr is used inste=
ad.=C2=A0 The documentation says both ldaxr/stlxr provides one-way barriers=
.=C2=A0 Read/writes after ldaxr will be observed after, and read/writes bef=
ore stlxr will be observed before.=C2=A0 So, a pair of these instructions p=
rovides a full memory barrier.=C2=A0 However, if we don&#39;t observe the e=
xpected value, only ldaxr gets executed.=C2=A0 So, an unsuccessful pg_atomi=
c_compare_exchange_u64() attempt will leave us with a one-way barrier, and =
that caused a bug in my case.=C2=A0 In contrast, __sync_val_compare_and_swa=
p() uses=C2=A0__aarch64_cas8_sync, which is quite the same as __aarch64_cas=
8_acq_rel, but has an explicit memory barrier in the end.<div><br></div><di=
v>I have a couple of ideas on how to fix this problem.</div><div>1. Provide=
 full barrier semantics for pg_atomic_compare_exchange_*().=C2=A0 In partic=
ular, for __atomic_compare_exchange_n(), we should probably use=C2=A0__ATOM=
IC_ACQ_REL for success and run an explicit memory barrier in the case of fa=
ilure.</div><div>2. Document that pg_atomic_compare_exchange_*() doesn&#39;=
t necessarily provide a memory barrier on failure.=C2=A0 But then we need t=
o carefully check if existing use-cases need explicit memory barriers now.<=
/div><div><br></div><div>Any thoughts?</div><div><div><br></div><div><div>L=
inks<br>1. <a href=3D"https://www.postgresql.org/message-id/CAPpHfdsWcQb-u-=
9K%3DipneBf8CMhoUuBWKYc%2BXWJEHVdtONOepQ%40mail.gmail.com">https://www.post=
gresql.org/message-id/CAPpHfdsWcQb-u-9K%3DipneBf8CMhoUuBWKYc%2BXWJEHVdtONOe=
pQ%40mail.gmail.com</a></div><div>2.=C2=A0<a href=3D"https://developer.arm.=
com/documentation/100941/0101/Barriers">https://developer.arm.com/documenta=
tion/100941/0101/Barriers</a><br><br>------<br>Regards,<br>Alexander Korotk=
ov<br>Supabase</div></div></div></div></div>

--0000000000009e97e7062fc289bf--