On 28/06/2019 01:02, Thomas Munro wrote:
On Thu, Jun 27, 2019 at 11:38 PM Heikki Linnakangas <hlinn...@iki.fi> wrote:* I moved the logic to extend a 32-bit XID to 64-bits to a new helper function in varsup.c.I'm a bit uneasy about making this into a generally available function for reuse. I think we should instead come up with a very small number of sources of fxids that known to be free of races because of some well explained interlocking. For example, I believe it is safe to convert an xid obtained from a WAL record during recovery, because (for now) recovery is a single thread of execution and the next fxid can't advance underneath you. So I think XLogRecGetFullXid(XLogReaderState *record)[1] as I'm about to propose in another thread (though I've forgotten who wrote it, maybe Andres, Amit or me, but if it wasn't me then it's exactly what I would have written) is a safe blessed source of fxids. The rationale for writing this function instead of an earlier code that looked much like your proposed helper function, during EDB-internal review of zheap stuff, was this: if we provide a general purpose xid->fxid facility, it's virtually guaranteed that someone will eventually use it to shoot footwards, by acquiring an xid from somewhere, and then some arbitrary time later extending it to a fxid when no interlocking guarantees that the later conversion has the correct epoch.
Fair point.
I'd like to figure out how to maintain full versions of the procarray.c-managed xid horizons, without widening the shared memory representation. I was planning to think harder about for 13. Obviously that doesn't help you now. So I'm wondering if you should just open-code this for now, and put in a comment about why it's safe and a note that there'll hopefully be a fxid horizon available in a later release?
I came up with the attached. Instead of having a general purpose "widen" function, it adds GetFullRecentGlobalXmin(), to return a 64-bit version of RecentGlobalXmin. That's enough for this Gist vacuum patch.
In addition to that change, I modified the GistPageSetDeleted(), GistPageSetDeleteXid(), GistPageGetDeleteXid() inline functions a bit. I merged GistPageSetDeleted() and GistPageSetDeleteXid() into a single function, to make sure that the delete-XID is always set when a page is marked as deleted. And I modified GistPageGetDeleteXid() to return NormalTransactionId (or a FullTransactionId version of it, to be precise), for Gist pages that were deleted with older PostgreSQL v12 beta versions. The previous patch tripped an assertion in that case, which is not nice for people binary-upgrading from earlier beta versions.
I did some testing of this with XID wraparound, and it seems to work. I used the attached bash script for the testing, with the a helper contrib module to consume XIDs faster. It's not very well commented and probably not too useful for anyone, but I'm attaching it here mainly as a note to future-self, if we need to revisit this.
Unless something comes up, I'll commit this tomorrow. - Heikki
>From bdeb2467211a1ab9e733e070d54dce97c05cf18c Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakan...@iki.fi>
Date: Mon, 22 Jul 2019 15:57:01 +0300
Subject: [PATCH 1/2] Refactor checks for deleted GiST pages.
The explicit check in gistScanPage() isn't currently really necessary, as
a deleted page is always empty, so the loop would fall through without
doing anything, anyway. But it's a marginal optimization, and it gives a
nice place to attach a comment to explain how it works.
---
src/backend/access/gist/gist.c | 40 ++++++++++++-------------------
src/backend/access/gist/gistget.c | 14 +++++++++++
2 files changed, 29 insertions(+), 25 deletions(-)
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 169bf6fcfed..e9ca4b82527 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -709,14 +709,15 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace,
continue;
}
- if (stack->blkno != GIST_ROOT_BLKNO &&
- stack->parent->lsn < GistPageGetNSN(stack->page))
+ if ((stack->blkno != GIST_ROOT_BLKNO &&
+ stack->parent->lsn < GistPageGetNSN(stack->page)) ||
+ GistPageIsDeleted(stack->page))
{
/*
- * Concurrent split detected. There's no guarantee that the
- * downlink for this page is consistent with the tuple we're
- * inserting anymore, so go back to parent and rechoose the best
- * child.
+ * Concurrent split or page deletion detected. There's no
+ * guarantee that the downlink for this page is consistent with
+ * the tuple we're inserting anymore, so go back to parent and
+ * rechoose the best child.
*/
UnlockReleaseBuffer(stack->buffer);
xlocked = false;
@@ -735,9 +736,6 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace,
GISTInsertStack *item;
OffsetNumber downlinkoffnum;
- /* currently, internal pages are never deleted */
- Assert(!GistPageIsDeleted(stack->page));
-
downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
iid = PageGetItemId(stack->page, downlinkoffnum);
idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
@@ -858,12 +856,13 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace,
* leaf/inner is enough to recognize split for root
*/
}
- else if (GistFollowRight(stack->page) ||
- stack->parent->lsn < GistPageGetNSN(stack->page))
+ else if ((GistFollowRight(stack->page) ||
+ stack->parent->lsn < GistPageGetNSN(stack->page)) &&
+ GistPageIsDeleted(stack->page))
{
/*
- * The page was split while we momentarily unlocked the
- * page. Go back to parent.
+ * The page was split or deleted while we momentarily
+ * unlocked the page. Go back to parent.
*/
UnlockReleaseBuffer(stack->buffer);
xlocked = false;
@@ -872,18 +871,6 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace,
}
}
- /*
- * The page might have been deleted after we scanned the parent
- * and saw the downlink.
- */
- if (GistPageIsDeleted(stack->page))
- {
- UnlockReleaseBuffer(stack->buffer);
- xlocked = false;
- state.stack = stack = stack->parent;
- continue;
- }
-
/* now state.stack->(page, buffer and blkno) points to leaf page */
gistinserttuple(&state, stack, giststate, itup,
@@ -947,6 +934,9 @@ gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
break;
}
+ /* currently, internal pages are never deleted */
+ Assert(!GistPageIsDeleted(page));
+
top->lsn = BufferGetLSNAtomic(buffer);
/*
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 46d08e06350..c5fe2ea3998 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -377,6 +377,20 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
MemoryContextSwitchTo(oldcxt);
}
+ /*
+ * Check if the page was deleted after we saw the downlink. There's
+ * nothing of interest on a deleted page. Note that we must do this
+ * after checking the NSN for concurrent splits! It's possible that
+ * the page originally contained some tuples that are visible to use,
+ * but was split so that all the visible tuples were moved to another
+ * page, and then this page was deleted.
+ */
+ if (GistPageIsDeleted(page))
+ {
+ UnlockReleaseBuffer(buffer);
+ return;
+ }
+
so->nPageData = so->curPageData = 0;
scan->xs_hitup = NULL; /* might point into pageDataCxt */
if (so->pageDataCxt)
--
2.20.1
>From d9f03ccbf30eb25afac78771ba30690554dd97d6 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakan...@iki.fi>
Date: Mon, 22 Jul 2019 15:57:02 +0300
Subject: [PATCH 2/2] Use full 64-bit XID for checking if a deleted GiST page
is old enough.
Otherwise, after a deleted page gets even older, it becomes unrecyclable
again. B-tree has the same problem, and has had since time immemorial,
but let's at least fix this in GiST, where this is new.
---
src/backend/access/gist/gistutil.c | 24 ++++++++++++--
src/backend/access/gist/gistvacuum.c | 7 ++--
src/backend/access/gist/gistxlog.c | 32 ++++++++++++++----
src/backend/access/rmgrdesc/gistdesc.c | 11 ++++---
src/backend/utils/time/snapmgr.c | 30 +++++++++++++++++
src/include/access/gist.h | 45 +++++++++++++++++++++++---
src/include/access/gist_private.h | 4 +--
src/include/access/gistxlog.h | 6 ++--
src/include/utils/snapmgr.h | 3 ++
9 files changed, 134 insertions(+), 28 deletions(-)
diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.c
index 7d1b219bbc8..97260201dcd 100644
--- a/src/backend/access/gist/gistutil.c
+++ b/src/backend/access/gist/gistutil.c
@@ -882,9 +882,27 @@ gistNewBuffer(Relation r)
bool
gistPageRecyclable(Page page)
{
- return PageIsNew(page) ||
- (GistPageIsDeleted(page) &&
- TransactionIdPrecedes(GistPageGetDeleteXid(page), RecentGlobalXmin));
+ if (PageIsNew(page))
+ return true;
+ if (GistPageIsDeleted(page))
+ {
+ /*
+ * The page was deleted, but when? If it was just deleted, a scan
+ * might have seen the downlink to it, and will read the page later.
+ * As long as that can happen, we must keep the deleted page around as
+ * a tombstone.
+ *
+ * Compare the deletion XID with RecentGlobalXmin. If deleteXid <
+ * RecentGlobalXmin, then no scan that's still in progress could have
+ * seen its downlink, and we can recycle it.
+ */
+ FullTransactionId deletexid_full = GistPageGetDeleteXid(page);
+ FullTransactionId recentxmin_full = GetFullRecentGlobalXmin();
+
+ if (FullTransactionIdPrecedes(deletexid_full, recentxmin_full))
+ return true;
+ }
+ return false;
}
bytea *
diff --git a/src/backend/access/gist/gistvacuum.c b/src/backend/access/gist/gistvacuum.c
index 4270226eee2..bf754ea6d0d 100644
--- a/src/backend/access/gist/gistvacuum.c
+++ b/src/backend/access/gist/gistvacuum.c
@@ -595,7 +595,7 @@ gistdeletepage(IndexVacuumInfo *info, GistBulkDeleteResult *stats,
ItemId iid;
IndexTuple idxtuple;
XLogRecPtr recptr;
- TransactionId txid;
+ FullTransactionId txid;
/*
* Check that the leaf is still empty and deletable.
@@ -648,14 +648,13 @@ gistdeletepage(IndexVacuumInfo *info, GistBulkDeleteResult *stats,
* currently in progress must have ended. (That's much more conservative
* than needed, but let's keep it safe and simple.)
*/
- txid = ReadNewTransactionId();
+ txid = ReadNextFullTransactionId();
START_CRIT_SECTION();
/* mark the page as deleted */
MarkBufferDirty(leafBuffer);
- GistPageSetDeleteXid(leafPage, txid);
- GistPageSetDeleted(leafPage);
+ GistPageSetDeleted(leafPage, txid);
stats->stats.pages_deleted++;
/* remove the downlink from the parent */
diff --git a/src/backend/access/gist/gistxlog.c b/src/backend/access/gist/gistxlog.c
index 503db34d863..3b28f546465 100644
--- a/src/backend/access/gist/gistxlog.c
+++ b/src/backend/access/gist/gistxlog.c
@@ -356,8 +356,7 @@ gistRedoPageDelete(XLogReaderState *record)
{
Page page = (Page) BufferGetPage(leafBuffer);
- GistPageSetDeleteXid(page, xldata->deleteXid);
- GistPageSetDeleted(page);
+ GistPageSetDeleted(page, xldata->deleteXid);
PageSetLSN(page, lsn);
MarkBufferDirty(leafBuffer);
@@ -396,8 +395,27 @@ gistRedoPageReuse(XLogReaderState *record)
*/
if (InHotStandby)
{
- ResolveRecoveryConflictWithSnapshot(xlrec->latestRemovedXid,
- xlrec->node);
+ FullTransactionId latestRemovedFullXid = xlrec->latestRemovedFullXid;
+ FullTransactionId nextFullXid = ReadNextFullTransactionId();
+ uint64 diff;
+
+ /*
+ * ResolveRecoveryConflictWithSnapshot operates on 32-bit
+ * TransactionIds, so truncate the logged FullTransactionId. If the
+ * logged value is very old, so that XID wrap-around already happened
+ * on it, there can't be any snapshots that still see it.
+ */
+ nextFullXid = ReadNextFullTransactionId();
+ diff = U64FromFullTransactionId(nextFullXid) -
+ U64FromFullTransactionId(latestRemovedFullXid);
+ if (diff < MaxTransactionId / 2)
+ {
+ TransactionId latestRemovedXid;
+
+ latestRemovedXid = XidFromFullTransactionId(latestRemovedFullXid);
+ ResolveRecoveryConflictWithSnapshot(latestRemovedXid,
+ xlrec->node);
+ }
}
}
@@ -554,7 +572,7 @@ gistXLogSplit(bool page_is_leaf,
* downlink from the parent page.
*/
XLogRecPtr
-gistXLogPageDelete(Buffer buffer, TransactionId xid,
+gistXLogPageDelete(Buffer buffer, FullTransactionId xid,
Buffer parentBuffer, OffsetNumber downlinkOffset)
{
gistxlogPageDelete xlrec;
@@ -578,7 +596,7 @@ gistXLogPageDelete(Buffer buffer, TransactionId xid,
* Write XLOG record about reuse of a deleted page.
*/
void
-gistXLogPageReuse(Relation rel, BlockNumber blkno, TransactionId latestRemovedXid)
+gistXLogPageReuse(Relation rel, BlockNumber blkno, FullTransactionId latestRemovedXid)
{
gistxlogPageReuse xlrec_reuse;
@@ -591,7 +609,7 @@ gistXLogPageReuse(Relation rel, BlockNumber blkno, TransactionId latestRemovedXi
/* XLOG stuff */
xlrec_reuse.node = rel->rd_node;
xlrec_reuse.block = blkno;
- xlrec_reuse.latestRemovedXid = latestRemovedXid;
+ xlrec_reuse.latestRemovedFullXid = latestRemovedXid;
XLogBeginInsert();
XLogRegisterData((char *) &xlrec_reuse, SizeOfGistxlogPageReuse);
diff --git a/src/backend/access/rmgrdesc/gistdesc.c b/src/backend/access/rmgrdesc/gistdesc.c
index 767864b58e6..eccb6fd9428 100644
--- a/src/backend/access/rmgrdesc/gistdesc.c
+++ b/src/backend/access/rmgrdesc/gistdesc.c
@@ -26,10 +26,11 @@ out_gistxlogPageUpdate(StringInfo buf, gistxlogPageUpdate *xlrec)
static void
out_gistxlogPageReuse(StringInfo buf, gistxlogPageReuse *xlrec)
{
- appendStringInfo(buf, "rel %u/%u/%u; blk %u; latestRemovedXid %u",
+ appendStringInfo(buf, "rel %u/%u/%u; blk %u; latestRemovedXid %u:%u",
xlrec->node.spcNode, xlrec->node.dbNode,
xlrec->node.relNode, xlrec->block,
- xlrec->latestRemovedXid);
+ EpochFromFullTransactionId(xlrec->latestRemovedFullXid),
+ XidFromFullTransactionId(xlrec->latestRemovedFullXid));
}
static void
@@ -50,8 +51,10 @@ out_gistxlogPageSplit(StringInfo buf, gistxlogPageSplit *xlrec)
static void
out_gistxlogPageDelete(StringInfo buf, gistxlogPageDelete *xlrec)
{
- appendStringInfo(buf, "deleteXid %u; downlink %u",
- xlrec->deleteXid, xlrec->downlinkOffset);
+ appendStringInfo(buf, "deleteXid %u:%u; downlink %u",
+ EpochFromFullTransactionId(xlrec->deleteXid),
+ XidFromFullTransactionId(xlrec->deleteXid),
+ xlrec->downlinkOffset);
}
void
diff --git a/src/backend/utils/time/snapmgr.c b/src/backend/utils/time/snapmgr.c
index 6690d781379..35d99857871 100644
--- a/src/backend/utils/time/snapmgr.c
+++ b/src/backend/utils/time/snapmgr.c
@@ -956,6 +956,36 @@ xmin_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
return 0;
}
+/*
+ * Get current RecentGlobalXmin value, as a FullTransactionId.
+ */
+FullTransactionId
+GetFullRecentGlobalXmin(void)
+{
+ FullTransactionId nextxid_full;
+ uint32 nextxid_epoch;
+ TransactionId nextxid_xid;
+ uint32 epoch;
+
+ Assert(TransactionIdIsNormal(RecentGlobalXmin));
+
+ /*
+ * Compute the epoch of the target xid from the next XID's epoch.
+ * This relies on the fact that RecentGlobalXmin must be within the 2
+ * billion XID horizon from the next XID.
+ */
+ nextxid_full = ReadNextFullTransactionId();
+ nextxid_epoch = EpochFromFullTransactionId(nextxid_full);
+ nextxid_xid = XidFromFullTransactionId(nextxid_full);
+
+ if (RecentGlobalXmin > nextxid_xid)
+ epoch = nextxid_epoch - 1;
+ else
+ epoch = nextxid_epoch;
+
+ return FullTransactionIdFromEpochAndXid(epoch, RecentGlobalXmin);
+}
+
/*
* SnapshotResetXmin
*
diff --git a/src/include/access/gist.h b/src/include/access/gist.h
index 6902f4115b7..8292956cc09 100644
--- a/src/include/access/gist.h
+++ b/src/include/access/gist.h
@@ -16,6 +16,7 @@
#ifndef GIST_H
#define GIST_H
+#include "access/transam.h"
#include "access/xlog.h"
#include "access/xlogdefs.h"
#include "storage/block.h"
@@ -140,8 +141,6 @@ typedef struct GISTENTRY
#define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page))
#define GistPageIsDeleted(page) ( GistPageGetOpaque(page)->flags & F_DELETED)
-#define GistPageSetDeleted(page) ( GistPageGetOpaque(page)->flags |= F_DELETED)
-#define GistPageSetNonDeleted(page) ( GistPageGetOpaque(page)->flags &= ~F_DELETED)
#define GistTuplesDeleted(page) ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
#define GistMarkTuplesDeleted(page) ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
@@ -158,9 +157,45 @@ typedef struct GISTENTRY
#define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
#define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))
-/* For deleted pages we store last xid which could see the page in scan */
-#define GistPageGetDeleteXid(page) ( ((PageHeader) (page))->pd_prune_xid )
-#define GistPageSetDeleteXid(page, val) ( ((PageHeader) (page))->pd_prune_xid = val)
+
+/*
+ * On a deleted page, we store this struct. A deleted page doesn't contain any
+ * tuples, so we don't use the normal page layout with line pointers. Instead,
+ * this struct is stored right after the standard page header. pd_lower points
+ * to the end of this struct. If we add fields to this struct in the future, we
+ * can distinguish the old and new formats by pd_lower.
+ */
+typedef struct GISTDeletedPageContents
+{
+ /* last xid which could see the page in a scan */
+ FullTransactionId deleteXid;
+} GISTDeletedPageContents;
+
+static inline void
+GistPageSetDeleted(Page page, FullTransactionId deletexid)
+{
+ Assert(PageIsEmpty(page));
+
+ GistPageGetOpaque(page)->flags |= F_DELETED;
+ ((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);
+
+ ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid = deletexid;
+}
+
+static inline FullTransactionId
+GistPageGetDeleteXid(Page page)
+{
+ Assert(GistPageIsDeleted(page));
+
+ /* Is the deleteXid field present? */
+ if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
+ offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
+ {
+ return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
+ }
+ else
+ return FullTransactionIdFromEpochAndXid(0, FirstNormalTransactionId);
+}
/*
* Vector of GISTENTRY structs; user-defined methods union and picksplit
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h
index 9e3958398ef..0488d01c9b8 100644
--- a/src/include/access/gist_private.h
+++ b/src/include/access/gist_private.h
@@ -426,11 +426,11 @@ extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
/* gistxlog.c */
extern XLogRecPtr gistXLogPageDelete(Buffer buffer,
- TransactionId xid, Buffer parentBuffer,
+ FullTransactionId xid, Buffer parentBuffer,
OffsetNumber downlinkOffset);
extern void gistXLogPageReuse(Relation rel, BlockNumber blkno,
- TransactionId latestRemovedXid);
+ FullTransactionId latestRemovedXid);
extern XLogRecPtr gistXLogUpdate(Buffer buffer,
OffsetNumber *todelete, int ntodelete,
diff --git a/src/include/access/gistxlog.h b/src/include/access/gistxlog.h
index 969a5376b5e..e44922d915c 100644
--- a/src/include/access/gistxlog.h
+++ b/src/include/access/gistxlog.h
@@ -83,7 +83,7 @@ typedef struct gistxlogPageSplit
*/
typedef struct gistxlogPageDelete
{
- TransactionId deleteXid; /* last Xid which could see page in scan */
+ FullTransactionId deleteXid; /* last Xid which could see page in scan */
OffsetNumber downlinkOffset; /* Offset of downlink referencing this
* page */
} gistxlogPageDelete;
@@ -98,10 +98,10 @@ typedef struct gistxlogPageReuse
{
RelFileNode node;
BlockNumber block;
- TransactionId latestRemovedXid;
+ FullTransactionId latestRemovedFullXid;
} gistxlogPageReuse;
-#define SizeOfGistxlogPageReuse (offsetof(gistxlogPageReuse, latestRemovedXid) + sizeof(TransactionId))
+#define SizeOfGistxlogPageReuse (offsetof(gistxlogPageReuse, latestRemovedFullXid) + sizeof(FullTransactionId))
extern void gist_redo(XLogReaderState *record);
extern void gist_desc(StringInfo buf, XLogReaderState *record);
diff --git a/src/include/utils/snapmgr.h b/src/include/utils/snapmgr.h
index 58ae3b0c7a1..6641ee510a1 100644
--- a/src/include/utils/snapmgr.h
+++ b/src/include/utils/snapmgr.h
@@ -13,6 +13,7 @@
#ifndef SNAPMGR_H
#define SNAPMGR_H
+#include "access/transam.h"
#include "fmgr.h"
#include "utils/relcache.h"
#include "utils/resowner.h"
@@ -122,6 +123,8 @@ extern void UnregisterSnapshot(Snapshot snapshot);
extern Snapshot RegisterSnapshotOnOwner(Snapshot snapshot, ResourceOwner owner);
extern void UnregisterSnapshotFromOwner(Snapshot snapshot, ResourceOwner owner);
+extern FullTransactionId GetFullRecentGlobalXmin(void);
+
extern void AtSubCommit_Snapshot(int level);
extern void AtSubAbort_Snapshot(int level);
extern void AtEOXact_Snapshot(bool isCommit, bool resetXmin);
--
2.20.1
gist-vacuum-wraparound-test.sh
Description: application/shellscript
xidtest.tar.gz
Description: application/gzip
