On Wed, Aug 16, 2023 at 05:30:59PM +0200, Michail Nikolaev wrote:
> Updated version (with read barriers is attached).
Thanks for the updated patch. I've attached v4 in which I've made a number
of cosmetic edits.
> I'll think more, but can't find something wrong here so far.
IIUC this memory barrier stuff is only applicable to KnownAssignedXidsAdd()
(without an exclusive lock) when we add entries to the end of the array and
then update the head pointer. Otherwise, appropriate locks are taken when
reading/writing the array. For example, say we have the following array:
head
|
v
[ 0, 1, 2, 3 ]
When adding elements, we keep the head pointer where it is:
head
|
v
[ 0, 1, 2, 3, 4, 5 ]
If another processor sees this intermediate state, it's okay because it
will only inspect elements 0 through 3. Only at the end do we update the
head pointer:
head
|
v
[ 0, 1, 2, 3, 4, 5 ]
With weak memory ordering and no barriers, another process may see this
(which is obviously no good):
head
|
v
[ 0, 1, 2, 3 ]
One thing that I'm still trying to understand is this code in
KnownAssignedXidsSearch():
/* we hold ProcArrayLock exclusively, so no need for spinlock */
tail = pArray->tailKnownAssignedXids;
head = pArray->headKnownAssignedXids;
It's not clear to me why holding ProcArrayLock exclusively means we don't
need to worry about the spinlock/barriers. If KnownAssignedXidsAdd() adds
entries without a lock, holding ProcArrayLock won't protect you, and I
don't see anything else that acts as a read barrier before the array
entries are inspected.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
>From 11de5076adc060c0dde32e8538714301f9b98d02 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nat...@postgresql.org>
Date: Wed, 16 Aug 2023 10:52:56 -0700
Subject: [PATCH v4 1/1] Replace known_assigned_xids_lck with memory barriers.
Suggested-by: Tom Lane
Author: Michail Nikolaev
Discussion: https://postgr.es/m/CANtu0oh0si%3DjG5z_fLeFtmYcETssQ08kLEa8b6TQqDm_cinroA%40mail.gmail.com
---
src/backend/storage/ipc/procarray.c | 71 ++++++++++-------------------
1 file changed, 25 insertions(+), 46 deletions(-)
diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index 2a3da49b8f..a3def020b6 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -61,7 +61,6 @@
#include "port/pg_lfind.h"
#include "storage/proc.h"
#include "storage/procarray.h"
-#include "storage/spin.h"
#include "utils/acl.h"
#include "utils/builtins.h"
#include "utils/rel.h"
@@ -82,7 +81,6 @@ typedef struct ProcArrayStruct
int numKnownAssignedXids; /* current # of valid entries */
int tailKnownAssignedXids; /* index of oldest valid element */
int headKnownAssignedXids; /* index of newest element, + 1 */
- slock_t known_assigned_xids_lck; /* protects head/tail pointers */
/*
* Highest subxid that has been removed from KnownAssignedXids array to
@@ -441,7 +439,6 @@ CreateSharedProcArray(void)
procArray->numKnownAssignedXids = 0;
procArray->tailKnownAssignedXids = 0;
procArray->headKnownAssignedXids = 0;
- SpinLockInit(&procArray->known_assigned_xids_lck);
procArray->lastOverflowedXid = InvalidTransactionId;
procArray->replication_slot_xmin = InvalidTransactionId;
procArray->replication_slot_catalog_xmin = InvalidTransactionId;
@@ -4561,14 +4558,10 @@ KnownAssignedTransactionIdsIdleMaintenance(void)
* during normal running). Compressing unused entries out of the array
* likewise requires exclusive lock. To add XIDs to the array, we just insert
* them into slots to the right of the head pointer and then advance the head
- * pointer. This wouldn't require any lock at all, except that on machines
- * with weak memory ordering we need to be careful that other processors
- * see the array element changes before they see the head pointer change.
- * We handle this by using a spinlock to protect reads and writes of the
- * head/tail pointers. (We could dispense with the spinlock if we were to
- * create suitable memory access barrier primitives and use those instead.)
- * The spinlock must be taken to read or write the head/tail pointers unless
- * the caller holds ProcArrayLock exclusively.
+ * pointer. This doesn't require any lock at all, but on machines with weak
+ * memory ordering, we need to be careful that other processors see the array
+ * element changes before they see the head pointer change. We handle this by
+ * using memory barriers.
*
* Algorithmic analysis:
*
@@ -4806,22 +4799,15 @@ KnownAssignedXidsAdd(TransactionId from_xid, TransactionId to_xid,
pArray->numKnownAssignedXids += nxids;
/*
- * Now update the head pointer. We use a spinlock to protect this
- * pointer, not because the update is likely to be non-atomic, but to
- * ensure that other processors see the above array updates before they
- * see the head pointer change.
- *
- * If we're holding ProcArrayLock exclusively, there's no need to take the
- * spinlock.
+ * Now update the head pointer. We use a write barrier to ensure that
+ * other processors see the above array updates before they see the head
+ * pointer change. The barrier isn't required if we're holding
+ * ProcArrayLock exclusively.
*/
- if (exclusive_lock)
- pArray->headKnownAssignedXids = head;
- else
- {
- SpinLockAcquire(&pArray->known_assigned_xids_lck);
- pArray->headKnownAssignedXids = head;
- SpinLockRelease(&pArray->known_assigned_xids_lck);
- }
+ if (!exclusive_lock)
+ pg_write_barrier();
+
+ pArray->headKnownAssignedXids = head;
}
/*
@@ -4843,20 +4829,15 @@ KnownAssignedXidsSearch(TransactionId xid, bool remove)
int tail;
int result_index = -1;
- if (remove)
- {
- /* we hold ProcArrayLock exclusively, so no need for spinlock */
- tail = pArray->tailKnownAssignedXids;
- head = pArray->headKnownAssignedXids;
- }
- else
- {
- /* take spinlock to ensure we see up-to-date array contents */
- SpinLockAcquire(&pArray->known_assigned_xids_lck);
- tail = pArray->tailKnownAssignedXids;
- head = pArray->headKnownAssignedXids;
- SpinLockRelease(&pArray->known_assigned_xids_lck);
- }
+ tail = pArray->tailKnownAssignedXids;
+ head = pArray->headKnownAssignedXids;
+
+ /*
+ * If we know that we're holding ProcArrayLock exclusively, we don't need
+ * the read barrier.
+ */
+ if (!remove)
+ pg_read_barrier(); /* pairs with KnownAssignedXidsAdd */
/*
* Standard binary search. Note we can ignore the KnownAssignedXidsValid
@@ -5094,13 +5075,11 @@ KnownAssignedXidsGetAndSetXmin(TransactionId *xarray, TransactionId *xmin,
* cannot enter and then leave the array while we hold ProcArrayLock. We
* might miss newly-added xids, but they should be >= xmax so irrelevant
* anyway.
- *
- * Must take spinlock to ensure we see up-to-date array contents.
*/
- SpinLockAcquire(&procArray->known_assigned_xids_lck);
tail = procArray->tailKnownAssignedXids;
head = procArray->headKnownAssignedXids;
- SpinLockRelease(&procArray->known_assigned_xids_lck);
+
+ pg_read_barrier(); /* pairs with KnownAssignedXidsAdd */
for (i = tail; i < head; i++)
{
@@ -5147,10 +5126,10 @@ KnownAssignedXidsGetOldestXmin(void)
/*
* Fetch head just once, since it may change while we loop.
*/
- SpinLockAcquire(&procArray->known_assigned_xids_lck);
tail = procArray->tailKnownAssignedXids;
head = procArray->headKnownAssignedXids;
- SpinLockRelease(&procArray->known_assigned_xids_lck);
+
+ pg_read_barrier(); /* pairs with KnownAssignedXidsAdd */
for (i = tail; i < head; i++)
{
--
2.25.1
