Feedback-ID: ic6394509:Fastmail
MIME-Version: 1.0
Date: Wed, 29 Oct 2025 11:33:07 +0100
From: "Joel Jacobson" <joel@compiler.org>
To: pgsql-hackers <pgsql-hackers@postgresql.org>
Message-Id: <7556f0d4-03fd-451a-bd34-5f62b424319a@app.fastmail.com>
In-Reply-To: <DF4BDA30-CC41-4BAF-9852-E399C3F273EC@gmail.com>
References: <6899c044-4a82-49be-8117-e6f669765f7e@app.fastmail.com>
 <165530.1752362320@sss.pgh.pa.us>
 <02a7cd37-e2fc-4212-8b19-f8c239c95fb8@app.fastmail.com>
 <e396ecf3-4227-4918-b9ff-e9568dcebcf0@app.fastmail.com>
 <b6a427fe-2ed6-4568-85d9-207a68172617@app.fastmail.com>
 <CAK80=jhmE40KVqQ3ho37MArS7cAED1p9m7uikDxcnDmqdW7t8A@mail.gmail.com>
 <96f00bf1-cc9d-4520-9d02-9e14e7767c88@app.fastmail.com>
 <30c2aa7d-dd6c-4b68-a2e4-f217a1a34acf@app.fastmail.com>
 <CA+hUKGLrMGkWDB0cwTa0RqD+AF7O-Ywgck8aVYKwOQnZgYRRug@mail.gmail.com>
 <0b4d402a-9ac2-4aa8-acf8-8231dbe579ea@app.fastmail.com>
 <c8e84bb2-d2e5-4a77-b547-3a93c5778e7e@app.fastmail.com>
 <3095599.1758644879@sss.pgh.pa.us>
 <0dc6a2cc-5216-4dc1-9dd2-430cafc6095b@app.fastmail.com>
 <E7D8A5CD-C445-4713-B6B7-6CC1D3A71161@gmail.com>
 <baf71275-9083-41be-ae13-f80821541a1a@app.fastmail.com>
 <52CC167F-763B-4ECA-B0B4-DAB381816828@gmail.com>
 <d35a114d-204a-4b40-9284-06749532b724@app.fastmail.com>
 <9186C6D0-F7A9-482A-9183-89E530B57E36@gmail.com>
 <da0996!!!!!!d8-ecf9-490d-bbd0-2a5bdb5b115a@app.fastmail.com>
 <D1CF7CA5-213A-4FC1-86DB-052D58904A0A@gmail.com>
 <cad78ff4-aae9-4c1c-8e16-ff0ccd4957f1@app.fastmail.com>
 <1073593.1759423179@sss.pgh.pa.us>
 <4bd5e6c4-6fa7-44bb-869d-59a32a331fa8@app.fastmail.com>
 <CAFY6G8dap-bCnAnMG-2Gzew8yv2Vbi9gsx9+yszKMmd57ygfvA@mail.gmail.com>
 <85828f29-e72e-4400-94f3-9a69bc8dc239@app.fastmail.com>
 <2495353.1759860890@sss.pgh.pa.us>
 <8aeae418-92a6-4bbd-9c06-9574c79e59f7@app.fastmail.com>
 <2531672.1759868124@sss.pgh.pa.us>
 <474efa78-337c-41cd-a73a-f845a0115109@app.fastmail.com>
 <2749343.1759949176@sss.pgh.pa.us>
 <8bfca2be-1ec0-4e15-aafb-0b7b661fe936@app.fastmail.com>
 <9eba307f-f2fb-48f0-9507-2e197f39ef9e@app.fastmail.com>
 <cde2a91d-d47a-43b5-ab27-f98aa739d38e@app.fastmail.com>
 <8c71183a-0d28-4bcf-a806-78446ff95404@app.fastmail.com>
 <1009807.1760476747@sss.pgh.pa.us>
 <1F7227F5-C33D-4E2C-8511-33F1468590D0@gmail.com>
 <0a5a20d3-4621-46b3-b2ab-903f63a20dea@app.fastmail.com>
 <6F913129-ABEF-4004-AAF3-F22FC34!29AE8@gmail.com>
 <cbabbb45-ec27-47f1-a8f3-eb29073e9aef@app.fastmail.com>
 <ceab2c54-3463-4029-a7d8-895a617bb457@app.fastmail.com>
 <1547585.1760645808@sss.pgh.pa.us>
 <b8df8040-1b15-4a1a-b5f6-74acebbd2d0c@app.fastmail.com>
 <CAE7r3MLivh1sHWF06hrVXkiQbw-KChPcQsh+9CheXprm5vRVMQ@mail.gmail.com>
 <14865EB6-0BF4-462B-9072-10BDAC10C052@gmail.com>
 <CAE7r3MK-3AOdh1mpZ8hw9h6F_i0D5RMoAy7CttnfCJRpB8GJDA@mail.gmail.com>
 <0BCA1C2D-B92C-459E-B1A6-6D06BA4C62CF@gmail.com>
 <55d24cbb-e9ef-491f-a99b-b3dbd7cecdf9@app.fastmail.com>
 <38574cad-e90d-47b7-a015-753bb6bbc360@app.fastmail.com>
 <66631FB7-5BEA-4ED5-A694-9AD8B9CCFEE8@gmail.com>
 <4b7b49a5-5e1a-44a8-93e0-60457d15cb1d@app.fastmail.com>
 <82DEA2B6-6FC5-4A79-BDE3-1FD72F104A6E@gmail.com>
 <38de1036-d8cf-420c-b845-edb5a946b191@app.fastmail.com>
 <87E40BF8-8877-4DBD-9040-99AF8A4E6358@gmail.com>
 <d29ae0a8-b28c-4450-bd9f-c56657e57f45@app.fastmail.com>
 <DF4BDA30-CC41-4BAF-9852-E399C3F273EC@gmail.com>
Subject: Re: Optimize LISTEN/NOTIFY
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/7556f0d4-03fd-451a-bd34-5f62b424319a%40app.fastmail.com>
Precedence: bulk

On Wed, Oct 29, 2025, at 08:05, Chao Li wrote:
>> On Oct 29, 2025, at 05:45, Joel Jacobson <joel@compiler.org> wrote:
>> I found a concurrency bug in v21 that could cause missed wakeup when a
>> backend would UNLISTEN on the last channel, which called
>> asyncQueueUnregister, and if wakeupPending was at that time already s=
et,
>> then it wouldn't get reset, since in ProcessIncomingNotify we return
>> early if (listenChannels =3D=3D NIL), so we would never clear wakeupP=
ending
>> which happens in asyncQueueReadAllNotifications.
>>=20
>> Fixed by clearing wakeupPending in asyncQueueUnregister:
>>=20
>> @@ -1597,6 +1597,7 @@ asyncQueueUnregister(void)
>>    /* Mark our entry as invalid */
>>    QUEUE_BACKEND_PID(MyProcNumber) =3D InvalidPid;
>>    QUEUE_BACKEND_DBOID(MyProcNumber) =3D InvalidOid;
>> +   QUEUE_BACKEND_WAKEUP_PENDING(MyProcNumber) =3D false;
>>    /* and remove it from the list */
>>    if (QUEUE_FIRST_LISTENER =3D=3D MyProcNumber)
>>        QUEUE_FIRST_LISTENER =3D QUEUE_NEXT_LISTENER(MyProcNumber);
>>=20
>> /Joel<0001-optimize_listen_notify-v22.patch><0002-optimize_listen_not=
ify-v22.patch>
>
> I think the current implementation still has a race problem.
>
> Let=E2=80=99s say notifier N1 notifies listener=E2=80=99s L1 to read m=
essage.
> L1 starts to read: it acquires the look, gets reading range, then=20
> releases the lock, start performs reading without holding the lock.
> Notifier N2 comes, N2 doesn=E2=80=99t have anything L1 is interested i=
n. N2 now=20
> holds the look, when it checks "if (QUEUE_POS_EQUAL(pos,=20
> queueHeadBeforeWrite))=E2=80=9D, here comes the race. Because the lock=
 is in=20
> N2=E2=80=99s hand, L1 cannot get the lock to update its pos, so "if=20
> (QUEUE_POS_EQUAL(pos, queueHeadBeforeWrite))=E2=80=9D will not be sati=
sfied, so=20
> direct advancement won=E2=80=99t happen.

I'm not sure I agree that qualifies as a race "problem" per se, since I
think that just sounds like a case where we would do an unnecessary
wakeup, right?

Without more sophisticated data structures (e.g. skip ranges) and
increased code complexity, there will always be cases where we will by
do unnecessary wakeups, which IMO need not be a design goal to
completely avoid, until we have benchmark data that indicates otherwise.

I think we should iterate by first trying to reason about correctness of
the code, trying to prove/disprove if a notifications could ever end up
not being delivered. The bug I fixed in v22 is an example of such a
case, that would cause a listening backend to never be awaken, since
notifiers would not signal it due to the pending wake that was not
cleared.

I wonder if there could be more such serious bugs in the current code. I
will focus my efforts now trying to answer that question. Would be
really nice if we could find a way to reason formally about this. I've
been looking into the P programming language, which seems suitable for
modeling and verifying these kind of asynchronous concurrency protocols,
I will give it a try.

/Joel