Rework the way multixact truncations work

>From cdc4f8f3341161b87a5d11171efb14c98c252ee6 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Thu, 4 Jun 2015 19:38:32 +0200
Subject: [PATCH 1/3] WIP-dontcommit: Add functions to burn multixacts

This should live in its own module, but we don't have that yet.
---
 contrib/pageinspect/heapfuncs.c          | 43 ++++++++++++++++++++++++++++++++
 contrib/pageinspect/pageinspect--1.3.sql |  6 +++++
 src/backend/access/heap/heapam.c         |  2 +-
 src/backend/access/transam/multixact.c   | 15 ++++++-----
 src/include/access/multixact.h           |  3 ++-
 5 files changed, 61 insertions(+), 8 deletions(-)

diff --git a/contrib/pageinspect/heapfuncs.c b/contrib/pageinspect/heapfuncs.c
index 8d1666c..7a3aa14 100644
--- a/contrib/pageinspect/heapfuncs.c
+++ b/contrib/pageinspect/heapfuncs.c
@@ -29,6 +29,8 @@
 #include "funcapi.h"
 #include "utils/builtins.h"
 #include "miscadmin.h"
+#include "access/multixact.h"
+#include "access/transam.h"
 
 
 /*
@@ -223,3 +225,44 @@ heap_page_items(PG_FUNCTION_ARGS)
 	else
 		SRF_RETURN_DONE(fctx);
 }
+
+extern Datum
+pg_burn_multixact(PG_FUNCTION_ARGS);
+PG_FUNCTION_INFO_V1(pg_burn_multixact);
+
+Datum
+pg_burn_multixact(PG_FUNCTION_ARGS)
+{
+	int		rep = PG_GETARG_INT32(0);
+	int		size = PG_GETARG_INT32(1);
+	MultiXactMember *members;
+	MultiXactId ret;
+	TransactionId id = ReadNewTransactionId() - size;
+	int		i;
+
+	if (rep < 1)
+		elog(ERROR, "need to burn, burn, burn");
+
+	members = palloc(size * sizeof(MultiXactMember));
+	for (i = 0; i < size; i++)
+	{
+		members[i].xid = id++;
+		members[i].status = MultiXactStatusForShare;
+
+		if (!TransactionIdIsNormal(members[i].xid))
+		{
+			id = FirstNormalTransactionId;
+			members[i].xid = id++;
+		}
+	}
+
+	MultiXactIdSetOldestMember();
+
+	for (i = 0; i < rep; i++)
+	{
+		CHECK_FOR_INTERRUPTS();
+		ret = MultiXactIdCreateFromMembers(size, members, true);
+	}
+
+	PG_RETURN_INT64((int64) ret);
+}
diff --git a/contrib/pageinspect/pageinspect--1.3.sql b/contrib/pageinspect/pageinspect--1.3.sql
index a99e058..22f51bc 100644
--- a/contrib/pageinspect/pageinspect--1.3.sql
+++ b/contrib/pageinspect/pageinspect--1.3.sql
@@ -187,3 +187,9 @@ CREATE FUNCTION gin_leafpage_items(IN page bytea,
 RETURNS SETOF record
 AS 'MODULE_PATHNAME', 'gin_leafpage_items'
 LANGUAGE C STRICT;
+
+
+CREATE FUNCTION pg_burn_multixact(num int4, size int4)
+RETURNS int4
+AS 'MODULE_PATHNAME', 'pg_burn_multixact'
+LANGUAGE C STRICT;
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index caacc10..c57f99d 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -6050,7 +6050,7 @@ FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
 		 * Create a new multixact with the surviving members of the previous
 		 * one, to set as new Xmax in the tuple.
 		 */
-		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers);
+		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers, false);
 		*flags |= FRM_RETURN_IS_MULTI;
 	}
 
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 377d084..cf43254 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -405,7 +405,7 @@ MultiXactIdCreate(TransactionId xid1, MultiXactStatus status1,
 	members[1].xid = xid2;
 	members[1].status = status2;
 
-	newMulti = MultiXactIdCreateFromMembers(2, members);
+	newMulti = MultiXactIdCreateFromMembers(2, members, false);
 
 	debug_elog3(DEBUG2, "Create: %s",
 				mxid_to_string(newMulti, 2, members));
@@ -471,7 +471,7 @@ MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
 		 */
 		member.xid = xid;
 		member.status = status;
-		newMulti = MultiXactIdCreateFromMembers(1, &member);
+		newMulti = MultiXactIdCreateFromMembers(1, &member, false);
 
 		debug_elog4(DEBUG2, "Expand: %u has no members, create singleton %u",
 					multi, newMulti);
@@ -523,7 +523,7 @@ MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
 
 	newMembers[j].xid = xid;
 	newMembers[j++].status = status;
-	newMulti = MultiXactIdCreateFromMembers(j, newMembers);
+	newMulti = MultiXactIdCreateFromMembers(j, newMembers, false);
 
 	pfree(members);
 	pfree(newMembers);
@@ -742,7 +742,7 @@ ReadNextMultiXactId(void)
  * NB: the passed members[] array will be sorted in-place.
  */
 MultiXactId
-MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
+MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members, bool nocache)
 {
 	MultiXactId multi;
 	MultiXactOffset offset;
@@ -761,7 +761,9 @@ MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
 	 * corner cases where someone else added us to a MultiXact without our
 	 * knowledge, but it's not worth checking for.)
 	 */
-	multi = mXactCacheGetBySet(nmembers, members);
+	multi = nocache ? InvalidMultiXactId :
+		mXactCacheGetBySet(nmembers, members);
+
 	if (MultiXactIdIsValid(multi))
 	{
 		debug_elog2(DEBUG2, "Create: in cache!");
@@ -834,7 +836,8 @@ MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
 	END_CRIT_SECTION();
 
 	/* Store the new MultiXactId in the local cache, too */
-	mXactCachePut(multi, nmembers, members);
+	if (!nocache)
+		mXactCachePut(multi, nmembers, members);
 
 	debug_elog2(DEBUG2, "Create: all done");
 
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index f1448fe..6213f8a 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -86,10 +86,11 @@ typedef struct xl_multixact_create
 extern MultiXactId MultiXactIdCreate(TransactionId xid1,
 				  MultiXactStatus status1, TransactionId xid2,
 				  MultiXactStatus status2);
+extern MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members, bool nocache);
 extern MultiXactId MultiXactIdExpand(MultiXactId multi, TransactionId xid,
 				  MultiXactStatus status);
 extern MultiXactId MultiXactIdCreateFromMembers(int nmembers,
-							 MultiXactMember *members);
+							 MultiXactMember *members, bool nocache);
 
 extern MultiXactId ReadNextMultiXactId(void);
 extern bool MultiXactIdIsRunning(MultiXactId multi, bool isLockOnly);
-- 
2.4.0.rc2.1.g3d6bc9a

>From ceb5683e62bcae51689dc27e0764f822e26595f7 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Mon, 15 Jun 2015 19:12:52 +0200
Subject: [PATCH 2/3] Lower *_freeze_max_age minimum values.

The old minimum values are rather large, making it time consuming to
test related behaviour. Additionally the current limits, especially for
multixacts, can be problematic in space-constrained systems. 10000000
multixacts can contain a lot of members.

Since there's no good reason for the current limits, lower them a good
bit. Setting them to 0 would be a bad idea, triggering endless vacuums,
so still retain a limit.
---
 src/backend/utils/misc/guc.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 230c5cc..aec4adc 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -2516,17 +2516,17 @@ static struct config_int ConfigureNamesInt[] =
 		},
 		&autovacuum_freeze_max_age,
 		/* see pg_resetxlog if you change the upper-limit value */
-		200000000, 100000000, 2000000000,
+		200000000, 100000, 2000000000,
 		NULL, NULL, NULL
 	},
 	{
-		/* see varsup.c for why this is PGC_POSTMASTER not PGC_SIGHUP */
+		/* see multixact.c for why this is PGC_POSTMASTER not PGC_SIGHUP */
 		{"autovacuum_multixact_freeze_max_age", PGC_POSTMASTER, AUTOVACUUM,
 			gettext_noop("Multixact age at which to autovacuum a table to prevent multixact wraparound."),
 			NULL
 		},
 		&autovacuum_multixact_freeze_max_age,
-		400000000, 10000000, 2000000000,
+		400000000, 10000, 2000000000,
 		NULL, NULL, NULL
 	},
 	{
-- 
2.4.0.rc2.1.g3d6bc9a

>From 482ac1f480cf9ffe8fe01f1ab94a95f9655b76bd Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Mon, 29 Jun 2015 21:47:42 +0200
Subject: [PATCH 3/3] Rework the way multixact truncations work.

The fact that multixact truncations are not WAL logged has caused a fair
share of problems. Amongst others it requires to do computations during
recovery while the database is not in a consistent state, delaying
truncations till checkpoints, and handling members being truncated, but
offset not.

We tried to put bandaids on lots of these issues over the last years,
but it seems time to change course. Thus this patch introduces WAL
logging for truncation, even in the back branches.

This allows:
1) to perform the truncation directly during VACUUM, instead of delaying it
   to the checkpoint.
2) to avoid looking at the offsets SLRU for truncation during recovery,
   we can just use the master's values.
3) simplify a fair amount of logic to keep in memory limits straight,
   this has gotten much easier

During the course of fixing this a bunch of bugs had to be fixed:
1) Data was not purged from memory the member's slru before deleting
   segments. This happend to be hard or impossible to hit due to the
   interlock between checkpoints and truncation.
2) find_multixact_start() relied on SimpleLruDoesPhysicalPageExist - but
   that doesn't work for offsets that haven't yet been flushed to
   disk. Flush out before running to fix. Not pretty, but it feels
   slightly safer to only make decisions based on on-disk state.
3) find_multixact_start() could be called concurrently with a truncation
   and thus fail. Via SetOffsetVacuumLimit() that could lead to a round
   of emergency vacuuming. The problem remains in
   pg_get_multixact_members(), but that's quite harmless.

To handle the case of an updated standby replaying WAL from a not-yet
upgraded primary we have to recognize that situation and use "old style"
truncation (i.e. looking at the SLRUs) during WAL replay. In contrast to
before this now happens in the startup process, when replaying a
checkpoint record, instead of the checkpointer. Doing this in the
restartpoint was incorrect, they can happen much later than the original
checkpoint, thereby leading to wraparound. It's also more in line to how
the WAL logging now works.

To avoid "multixact_redo: unknown op code 48" errors standbys should be
upgraded before primaries. This needs to be expressed clearly in the
release notes.

Backpatch to 9.3, where the use of multixacts was expanded. Arguably
this could be backpatched further, but there doesn't seem to be
sufficient benefit to outweigh the risk of applying a significantly
different patch there.
---
 src/backend/access/rmgrdesc/mxactdesc.c |  11 +
 src/backend/access/transam/multixact.c  | 601 ++++++++++++++++++--------------
 src/backend/access/transam/slru.c       |  83 ++++-
 src/backend/access/transam/xlog.c       |  53 +--
 src/backend/commands/vacuum.c           |   4 +-
 src/include/access/multixact.h          |  18 +-
 src/include/access/slru.h               |   4 +-
 src/include/storage/lwlock.h            |   3 +-
 src/tools/pgindent/typedefs.list        |   1 +
 9 files changed, 471 insertions(+), 307 deletions(-)

diff --git a/src/backend/access/rmgrdesc/mxactdesc.c b/src/backend/access/rmgrdesc/mxactdesc.c
index 572951e..e44e100 100644
--- a/src/backend/access/rmgrdesc/mxactdesc.c
+++ b/src/backend/access/rmgrdesc/mxactdesc.c
@@ -70,6 +70,14 @@ multixact_desc(StringInfo buf, XLogReaderState *record)
 		for (i = 0; i < xlrec->nmembers; i++)
 			out_member(buf, &xlrec->members[i]);
 	}
+	else if (info == XLOG_MULTIXACT_TRUNCATE_ID)
+	{
+		xl_multixact_truncate *xlrec = (xl_multixact_truncate *) rec;
+
+		appendStringInfo(buf, "offsets [%u, %u), members [%u, %u)",
+						 xlrec->startTruncOff, xlrec->endTruncOff,
+						 xlrec->startTruncMemb, xlrec->endTruncMemb);
+	}
 }
 
 const char *
@@ -88,6 +96,9 @@ multixact_identify(uint8 info)
 		case XLOG_MULTIXACT_CREATE_ID:
 			id = "CREATE_ID";
 			break;
+		case XLOG_MULTIXACT_TRUNCATE_ID:
+			id = "TRUNCATE";
+			break;
 	}
 
 	return id;
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index cf43254..7dfac45 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -49,9 +49,7 @@
  * value is removed; the cutoff value is stored in pg_class.  The minimum value
  * across all tables in each database is stored in pg_database, and the global
  * minimum across all databases is part of pg_control and is kept in shared
- * memory.  At checkpoint time, after the value is known flushed in WAL, any
- * files that correspond to multixacts older than that value are removed.
- * (These files are also removed when a restartpoint is executed.)
+ * memory.  Whenever that minimum is advanced, the SLRUs are truncated.
  *
  * When new multixactid values are to be created, care is taken that the
  * counter does not fall within the wraparound horizon considering the global
@@ -83,6 +81,7 @@
 #include "postmaster/autovacuum.h"
 #include "storage/lmgr.h"
 #include "storage/pmsignal.h"
+#include "storage/proc.h"
 #include "storage/procarray.h"
 #include "utils/builtins.h"
 #include "utils/memutils.h"
@@ -153,6 +152,7 @@
 
 /* page in which a member is to be found */
 #define MXOffsetToMemberPage(xid) ((xid) / (TransactionId) MULTIXACT_MEMBERS_PER_PAGE)
+#define MXOffsetToMemberSegment(xid) (MXOffsetToMemberPage(xid) / SLRU_PAGES_PER_SEGMENT)
 
 /* Location (byte offset within page) of flag word for a given member */
 #define MXOffsetToFlagsOffset(xid) \
@@ -218,11 +218,12 @@ typedef struct MultiXactStateData
 	bool		oldestOffsetKnown;
 
 	/*
-	 * This is what the previous checkpoint stored as the truncate position.
-	 * This value is the oldestMultiXactId that was valid when a checkpoint
-	 * was last executed.
+	 * True if a multixact truncation WAL record was replayed since the last
+	 * checkpoint. This is used to trigger 'legacy truncations', i.e. truncate
+	 * by looking at the data directory during WAL replay, when the primary is
+	 * too old to general truncation records.
 	 */
-	MultiXactId lastCheckpointedOldest;
+	bool		sawTruncationCkptCycle;
 
 	/* support for anti-wraparound measures */
 	MultiXactId multiVacLimit;
@@ -231,8 +232,7 @@ typedef struct MultiXactStateData
 	MultiXactId multiWrapLimit;
 
 	/* support for members anti-wraparound measures */
-	MultiXactOffset offsetStopLimit;
-	bool offsetStopLimitKnown;
+	MultiXactOffset offsetStopLimit;	/* known if oldestOffsetKnown */
 
 	/*
 	 * Per-backend data starts here.  We have two arrays stored in the area
@@ -362,12 +362,14 @@ static bool MultiXactOffsetPrecedes(MultiXactOffset offset1,
 						MultiXactOffset offset2);
 static void ExtendMultiXactOffset(MultiXactId multi);
 static void ExtendMultiXactMember(MultiXactOffset offset, int nmembers);
-static void DetermineSafeOldestOffset(MultiXactId oldestMXact);
 static bool MultiXactOffsetWouldWrap(MultiXactOffset boundary,
 						 MultiXactOffset start, uint32 distance);
-static bool SetOffsetVacuumLimit(bool finish_setup);
+static bool SetOffsetVacuumLimit(void);
 static bool find_multixact_start(MultiXactId multi, MultiXactOffset *result);
 static void WriteMZeroPageXlogRec(int pageno, uint8 info);
+static void WriteMTruncateXlogRec(Oid oldestMultiDB,
+					  MultiXactId startOff, MultiXactId endOff,
+					  MultiXactOffset startMemb, MultiXactOffset endMemb);
 
 
 /*
@@ -1100,7 +1102,7 @@ GetNewMultiXactId(int nmembers, MultiXactOffset *offset)
 	 *----------
 	 */
 #define OFFSET_WARN_SEGMENTS	20
-	if (MultiXactState->offsetStopLimitKnown &&
+	if (MultiXactState->oldestOffsetKnown &&
 		MultiXactOffsetWouldWrap(MultiXactState->offsetStopLimit, nextOffset,
 								 nmembers))
 	{
@@ -1140,7 +1142,7 @@ GetNewMultiXactId(int nmembers, MultiXactOffset *offset)
 			SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
 	}
 
-	if (MultiXactState->offsetStopLimitKnown &&
+	if (MultiXactState->oldestOffsetKnown &&
 		MultiXactOffsetWouldWrap(MultiXactState->offsetStopLimit,
 								 nextOffset,
 								 nmembers + MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT * OFFSET_WARN_SEGMENTS))
@@ -2018,13 +2020,21 @@ StartupMultiXact(void)
 void
 TrimMultiXact(void)
 {
-	MultiXactId multi = MultiXactState->nextMXact;
-	MultiXactOffset offset = MultiXactState->nextOffset;
-	MultiXactId	oldestMXact;
+	MultiXactId nextMXact;
+	MultiXactOffset offset;
+	MultiXactId oldestMXact;
+	MultiXactId oldestMXactDB;
 	int			pageno;
 	int			entryno;
 	int			flagsoff;
 
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	nextMXact = MultiXactState->nextMXact;
+	offset = MultiXactState->nextOffset;
+	oldestMXact = MultiXactState->oldestMultiXactId;
+	oldestMXactDB = MultiXactState->oldestMultiXactDB;
+	MultiXactState->finishedStartup = true;
+	LWLockRelease(MultiXactGenLock);
 
 	/* Clean up offsets state */
 	LWLockAcquire(MultiXactOffsetControlLock, LW_EXCLUSIVE);
@@ -2032,20 +2042,20 @@ TrimMultiXact(void)
 	/*
 	 * (Re-)Initialize our idea of the latest page number for offsets.
 	 */
-	pageno = MultiXactIdToOffsetPage(multi);
+	pageno = MultiXactIdToOffsetPage(nextMXact);
 	MultiXactOffsetCtl->shared->latest_page_number = pageno;
 
 	/*
 	 * Zero out the remainder of the current offsets page.  See notes in
 	 * TrimCLOG() for motivation.
 	 */
-	entryno = MultiXactIdToOffsetEntry(multi);
+	entryno = MultiXactIdToOffsetEntry(nextMXact);
 	if (entryno != 0)
 	{
 		int			slotno;
 		MultiXactOffset *offptr;
 
-		slotno = SimpleLruReadPage(MultiXactOffsetCtl, pageno, true, multi);
+		slotno = SimpleLruReadPage(MultiXactOffsetCtl, pageno, true, nextMXact);
 		offptr = (MultiXactOffset *) MultiXactOffsetCtl->shared->page_buffer[slotno];
 		offptr += entryno;
 
@@ -2094,12 +2104,11 @@ TrimMultiXact(void)
 
 	LWLockRelease(MultiXactMemberControlLock);
 
-	if (SetOffsetVacuumLimit(true) && IsUnderPostmaster)
-		SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	oldestMXact = MultiXactState->lastCheckpointedOldest;
-	LWLockRelease(MultiXactGenLock);
-	DetermineSafeOldestOffset(oldestMXact);
+	/*
+	 * Recompute limits as we are now fully started, we now can correctly
+	 * compute how far a members wraparound is away.
+	 */
+	SetMultiXactIdLimit(oldestMXact, oldestMXactDB);
 }
 
 /*
@@ -2268,8 +2277,19 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 	 (errmsg("MultiXactId wrap limit is %u, limited by database with OID %u",
 			 multiWrapLimit, oldest_datoid)));
 
+	/*
+	 * Computing the actual limits is only possible once the data directory is
+	 * in a consistent state. There's no need to compute the limits while
+	 * still replaying WAL as no new multis can be created anyway. So we'll
+	 * only do further checks after TrimMultiXact() has been called.
+	 */
+	if (!MultiXactState->finishedStartup)
+		return;
+
+	Assert(!InRecovery);
+
 	/* Set limits for offset vacuum. */
-	needs_offset_vacuum = SetOffsetVacuumLimit(false);
+	needs_offset_vacuum = SetOffsetVacuumLimit();
 
 	/*
 	 * If past the autovacuum force point, immediately signal an autovac
@@ -2279,11 +2299,11 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 	 * another iteration immediately if there are still any old databases.
 	 */
 	if ((MultiXactIdPrecedes(multiVacLimit, curMulti) ||
-		 needs_offset_vacuum) && IsUnderPostmaster && !InRecovery)
+		 needs_offset_vacuum) && IsUnderPostmaster)
 		SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
 
 	/* Give an immediate warning if past the wrap warn point */
-	if (MultiXactIdPrecedes(multiWarnLimit, curMulti) && !InRecovery)
+	if (MultiXactIdPrecedes(multiWarnLimit, curMulti))
 	{
 		char	   *oldest_datname;
 
@@ -2351,27 +2371,35 @@ MultiXactAdvanceNextMXact(MultiXactId minMulti,
 }
 
 /*
- * Update our oldestMultiXactId value, but only if it's more recent than
- * what we had.  However, even if not, always update the oldest multixact
- * offset limit.
+ * During WAL replay update our oldestMultiXactId value, but only if it's more
+ * recent than what we had.
  */
 void
 MultiXactAdvanceOldest(MultiXactId oldestMulti, Oid oldestMultiDB)
 {
+	Assert(InRecovery);
+
 	if (MultiXactIdPrecedes(MultiXactState->oldestMultiXactId, oldestMulti))
+	{
+		/*
+		 * If there has been a truncation on the master, detected via a moving
+		 * oldestMulti, without a corresponding truncation record we know that
+		 * the primary is still running an older version of postgres that
+		 * doesn't yet log multixact truncations. So perform truncation
+		 * ourselves.
+		 */
+		if (!MultiXactState->sawTruncationCkptCycle)
+		{
+			ereport(LOG,
+					(errmsg("performing legacy multixact truncation, upgrade master")));
+			TruncateMultiXact(oldestMulti, oldestMultiDB, true);
+		}
+
 		SetMultiXactIdLimit(oldestMulti, oldestMultiDB);
-}
+	}
 
-/*
- * Update the "safe truncation point".  This is the newest value of oldestMulti
- * that is known to be flushed as part of a checkpoint record.
- */
-void
-MultiXactSetSafeTruncate(MultiXactId safeTruncateMulti)
-{
-	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-	MultiXactState->lastCheckpointedOldest = safeTruncateMulti;
-	LWLockRelease(MultiXactGenLock);
+	/* only looked at in the startup process, no lock necessary */
+	MultiXactState->sawTruncationCkptCycle = false;
 }
 
 /*
@@ -2527,126 +2555,50 @@ GetOldestMultiXactId(void)
 }
 
 /*
- * Based on the given oldest MultiXactId, determine what's the oldest member
- * offset and install the limit info in MultiXactState, where it can be used to
- * prevent overrun of old data in the members SLRU area.
- */
-static void
-DetermineSafeOldestOffset(MultiXactId oldestMXact)
-{
-	MultiXactOffset oldestOffset;
-	MultiXactOffset nextOffset;
-	MultiXactOffset offsetStopLimit;
-	MultiXactOffset prevOffsetStopLimit;
-	MultiXactId		nextMXact;
-	bool			finishedStartup;
-	bool			prevOffsetStopLimitKnown;
-
-	/* Fetch values from shared memory. */
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	finishedStartup = MultiXactState->finishedStartup;
-	nextMXact = MultiXactState->nextMXact;
-	nextOffset = MultiXactState->nextOffset;
-	prevOffsetStopLimit = MultiXactState->offsetStopLimit;
-	prevOffsetStopLimitKnown = MultiXactState->offsetStopLimitKnown;
-	LWLockRelease(MultiXactGenLock);
-
-	/* Don't worry about this until after we've started up. */
-	if (!finishedStartup)
-		return;
-
-	/*
-	 * Determine the offset of the oldest multixact.  Normally, we can read
-	 * the offset from the multixact itself, but there's an important special
-	 * case: if there are no multixacts in existence at all, oldestMXact
-	 * obviously can't point to one.  It will instead point to the multixact
-	 * ID that will be assigned the next time one is needed.
-	 *
-	 * NB: oldestMXact should be the oldest multixact that still exists in the
-	 * SLRU, unlike in SetOffsetVacuumLimit, where we do this same computation
-	 * based on the oldest value that might be referenced in a table.
-	 */
-	if (nextMXact == oldestMXact)
-		oldestOffset = nextOffset;
-	else
-	{
-		bool		oldestOffsetKnown;
-
-		oldestOffsetKnown = find_multixact_start(oldestMXact, &oldestOffset);
-		if (!oldestOffsetKnown)
-		{
-			ereport(LOG,
-					(errmsg("MultiXact member wraparound protections are disabled because oldest checkpointed MultiXact %u does not exist on disk",
-						oldestMXact)));
-			return;
-		}
-	}
-
-	/* move back to start of the corresponding segment */
-	offsetStopLimit = oldestOffset - (oldestOffset %
-		(MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT));
-	/* always leave one segment before the wraparound point */
-	offsetStopLimit -= (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT);
-
-	/* if nothing has changed, we're done */
-	if (prevOffsetStopLimitKnown && offsetStopLimit == prevOffsetStopLimit)
-		return;
-
-	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-	MultiXactState->offsetStopLimit = offsetStopLimit;
-	MultiXactState->offsetStopLimitKnown = true;
-	LWLockRelease(MultiXactGenLock);
-
-	if (!prevOffsetStopLimitKnown && IsUnderPostmaster)
-		ereport(LOG,
-				(errmsg("MultiXact member wraparound protections are now enabled")));
-	ereport(DEBUG1,
-			(errmsg("MultiXact member stop limit is now %u based on MultiXact %u",
-				offsetStopLimit, oldestMXact)));
-}
-
-/*
  * Determine how aggressively we need to vacuum in order to prevent member
  * wraparound.
  *
- * To determine the oldest multixact ID, we look at oldestMultiXactId, not
- * lastCheckpointedOldest.  That's because vacuuming can't help with anything
- * older than oldestMultiXactId; anything older than that isn't referenced
- * by any table.  Offsets older than oldestMultiXactId but not as old as
- * lastCheckpointedOldest will go away after the next checkpoint.
+ * To do so determine what's the oldest member offset and install the limit
+ * info in MultiXactState, where it can be used to prevent overrun of old data
+ * in the members SLRU area.
  *
  * The return value is true if emergency autovacuum is required and false
  * otherwise.
  */
 static bool
-SetOffsetVacuumLimit(bool finish_setup)
+SetOffsetVacuumLimit(void)
 {
-	MultiXactId	oldestMultiXactId;
+	MultiXactId oldestMultiXactId;
 	MultiXactId nextMXact;
-	bool		finishedStartup;
-	MultiXactOffset oldestOffset = 0;		/* placate compiler */
+	MultiXactOffset oldestOffset = 0;	/* placate compiler */
+	MultiXactOffset prevOldestOffset;
 	MultiXactOffset nextOffset;
 	bool		oldestOffsetKnown = false;
-	MultiXactOffset prevOldestOffset;
 	bool		prevOldestOffsetKnown;
+	MultiXactOffset offsetStopLimit = 0;
+
+	/*
+	 * NB: Have to prevent concurrent truncation, we might otherwise try to
+	 * lookup a oldestMulti that's concurrently getting truncated away.
+	 */
+	LWLockAcquire(MultiXactTruncationLock, LW_SHARED);
 
 	/* Read relevant fields from shared memory. */
 	LWLockAcquire(MultiXactGenLock, LW_SHARED);
 	oldestMultiXactId = MultiXactState->oldestMultiXactId;
 	nextMXact = MultiXactState->nextMXact;
 	nextOffset = MultiXactState->nextOffset;
-	finishedStartup = MultiXactState->finishedStartup;
-	prevOldestOffset = MultiXactState->oldestOffset;
 	prevOldestOffsetKnown = MultiXactState->oldestOffsetKnown;
+	prevOldestOffset = MultiXactState->oldestOffset;
+	Assert(MultiXactState->finishedStartup);
 	LWLockRelease(MultiXactGenLock);
 
-	/* Don't do this until after any recovery is complete. */
-	if (!finishedStartup && !finish_setup)
-		return false;
-
 	/*
-	 * If no multixacts exist, then oldestMultiXactId will be the next
-	 * multixact that will be created, rather than an existing multixact.
+	 * Determine the offset of the oldest multixact.  Normally, we can read
+	 * the offset from the multixact itself, but there's an important special
+	 * case: if there are no multixacts in existence at all, oldestMXact
+	 * obviously can't point to one.  It will instead point to the multixact
+	 * ID that will be assigned the next time one is needed.
 	 */
 	if (oldestMultiXactId == nextMXact)
 	{
@@ -2667,34 +2619,48 @@ SetOffsetVacuumLimit(bool finish_setup)
 		 */
 		oldestOffsetKnown =
 			find_multixact_start(oldestMultiXactId, &oldestOffset);
+
+		if (oldestOffsetKnown)
+			ereport(DEBUG1,
+					(errmsg("oldest MultiXactId member is at offset %u",
+							oldestOffset)));
+		else
+			ereport(LOG,
+					(errmsg("MultiXact member wraparound protections are disabled because oldest checkpointed MultiXact %u does not exist on disk",
+							oldestMultiXactId)));
 	}
 
+	LWLockRelease(MultiXactTruncationLock);
+
 	/*
-	 * Except when initializing the system for the first time, there's no
-	 * need to update anything if we don't know the oldest offset or if it
-	 * hasn't changed.
+	 * If we can, compute limits (and install them MultiXactState) to prevent
+	 * overrun of old data in the members SLRU area. We can only do so if the
+	 * oldest offset is known though.
 	 */
-	if (finish_setup ||
-		(oldestOffsetKnown && !prevOldestOffsetKnown) ||
-		(oldestOffsetKnown && prevOldestOffset != oldestOffset))
+	if (oldestOffsetKnown)
 	{
-		/* Install the new limits. */
-		LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-		MultiXactState->oldestOffset = oldestOffset;
-		MultiXactState->oldestOffsetKnown = oldestOffsetKnown;
-		MultiXactState->finishedStartup = true;
-		LWLockRelease(MultiXactGenLock);
+		/* move back to start of the corresponding segment */
+		offsetStopLimit = oldestOffset - (oldestOffset %
+					  (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT));
 
-		/* Log the info */
-		if (oldestOffsetKnown)
-			ereport(DEBUG1,
-					(errmsg("oldest MultiXactId member is at offset %u",
-						oldestOffset)));
-		else
-			ereport(DEBUG1,
-					(errmsg("oldest MultiXactId member offset unknown")));
+		/* always leave one segment before the wraparound point */
+		offsetStopLimit -= (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT);
+
+		if (!prevOldestOffsetKnown && IsUnderPostmaster)
+			ereport(LOG,
+					(errmsg("MultiXact member wraparound protections are now enabled")));
+		ereport(DEBUG1,
+		(errmsg("MultiXact member stop limit is now %u based on MultiXact %u",
+				offsetStopLimit, oldestMultiXactId)));
 	}
 
+	/* Install the computed values */
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	MultiXactState->oldestOffset = oldestOffset;
+	MultiXactState->oldestOffsetKnown = oldestOffsetKnown;
+	MultiXactState->offsetStopLimit = offsetStopLimit;
+	LWLockRelease(MultiXactGenLock);
+
 	/*
 	 * If we failed to get the oldest offset this time, but we have a value
 	 * from a previous pass through this function, assess the need for
@@ -2721,7 +2687,7 @@ SetOffsetVacuumLimit(bool finish_setup)
  * boundary point, hence the name.  The reason we don't want to use the regular
  * 2^31-modulo arithmetic here is that we want to be able to use the whole of
  * the 2^32-1 space here, allowing for more multixacts that would fit
- * otherwise.  See also SlruScanDirCbRemoveMembers.
+ * otherwise.
  */
 static bool
 MultiXactOffsetWouldWrap(MultiXactOffset boundary, MultiXactOffset start,
@@ -2767,6 +2733,9 @@ MultiXactOffsetWouldWrap(MultiXactOffset boundary, MultiXactOffset start,
  *
  * Returns false if the file containing the multi does not exist on disk.
  * Otherwise, returns true and sets *result to the starting member offset.
+ *
+ * This function does not prevent concurrent truncation, so if that's
+ * required, the caller has to protect against that.
  */
 static bool
 find_multixact_start(MultiXactId multi, MultiXactOffset *result)
@@ -2777,9 +2746,21 @@ find_multixact_start(MultiXactId multi, MultiXactOffset *result)
 	int			slotno;
 	MultiXactOffset *offptr;
 
+	/* XXX: Remove || Startup after WAL page magic bump */
+	Assert(MultiXactState->finishedStartup || AmStartupProcess());
+
 	pageno = MultiXactIdToOffsetPage(multi);
 	entryno = MultiXactIdToOffsetEntry(multi);
 
+	/*
+	 * We need to flush out dirty data, so PhysicalPageExists can work
+	 * correctly, but SimpleLruFlush() is a pretty big hammer for that.
+	 * Alternatively we could add a in-memory version of page exists, but
+	 * find_multixact_start is called infrequently, and it doesn't seem bad to
+	 * flush buffers to disk before truncation.
+	 */
+	SimpleLruFlush(MultiXactOffsetCtl, true);
+
 	if (!SimpleLruDoesPhysicalPageExist(MultiXactOffsetCtl, pageno))
 		return false;
 
@@ -2885,65 +2866,6 @@ MultiXactMemberFreezeThreshold(void)
 	return multixacts - victim_multixacts;
 }
 
-/*
- * SlruScanDirectory callback.
- *		This callback deletes segments that are outside the range determined by
- *		the given page numbers.
- *
- * Both range endpoints are exclusive (that is, segments containing any of
- * those pages are kept.)
- */
-typedef struct MembersLiveRange
-{
-	int			rangeStart;
-	int			rangeEnd;
-} MembersLiveRange;
-
-static bool
-SlruScanDirCbRemoveMembers(SlruCtl ctl, char *filename, int segpage,
-						   void *data)
-{
-	MembersLiveRange *range = (MembersLiveRange *) data;
-	MultiXactOffset nextOffset;
-
-	if ((segpage == range->rangeStart) ||
-		(segpage == range->rangeEnd))
-		return false;			/* easy case out */
-
-	/*
-	 * To ensure that no segment is spuriously removed, we must keep track of
-	 * new segments added since the start of the directory scan; to do this,
-	 * we update our end-of-range point as we run.
-	 *
-	 * As an optimization, we can skip looking at shared memory if we know for
-	 * certain that the current segment must be kept.  This is so because
-	 * nextOffset never decreases, and we never increase rangeStart during any
-	 * one run.
-	 */
-	if (!((range->rangeStart > range->rangeEnd &&
-		   segpage > range->rangeEnd && segpage < range->rangeStart) ||
-		  (range->rangeStart < range->rangeEnd &&
-		   (segpage < range->rangeStart || segpage > range->rangeEnd))))
-		return false;
-
-	/*
-	 * Update our idea of the end of the live range.
-	 */
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	nextOffset = MultiXactState->nextOffset;
-	LWLockRelease(MultiXactGenLock);
-	range->rangeEnd = MXOffsetToMemberPage(nextOffset);
-
-	/* Recheck the deletion condition.  If it still holds, perform deletion */
-	if ((range->rangeStart > range->rangeEnd &&
-		 segpage > range->rangeEnd && segpage < range->rangeStart) ||
-		(range->rangeStart < range->rangeEnd &&
-		 (segpage < range->rangeStart || segpage > range->rangeEnd)))
-		SlruDeleteSegment(ctl, filename);
-
-	return false;				/* keep going */
-}
-
 typedef struct mxtruncinfo
 {
 	int			earliestExistingPage;
@@ -2967,6 +2889,35 @@ SlruScanDirCbFindEarliest(SlruCtl ctl, char *filename, int segpage, void *data)
 	return false;				/* keep going */
 }
 
+
+/*
+ * Delete member segments [oldest, oldestAlive)
+ */
+static void
+PerformMembersTruncation(MultiXactOffset oldestOffset, MultiXactOffset oldestAliveOffset)
+{
+	const int	maxsegment = MXOffsetToMemberSegment(MaxMultiXactOffset);
+	int			startsegment = MXOffsetToMemberSegment(oldestOffset);
+	int			endsegment = MXOffsetToMemberSegment(oldestAliveOffset);
+	int			segment = startsegment;
+
+	/*
+	 * Delete all the segments but the last one. The last segment can still
+	 * contains, possibly partially, valid data.
+	 */
+	while (segment != endsegment)
+	{
+		elog(DEBUG2, "truncating multixact members segment %x", segment);
+		SlruDeleteSegment(MultiXactMemberCtl, segment);
+
+		/* move to next segment, handling wraparound correctly */
+		if (segment == maxsegment)
+			segment = 0;
+		else
+			segment += 1;
+	}
+}
+
 /*
  * Remove all MultiXactOffset and MultiXactMember segments before the oldest
  * ones still of interest.
@@ -2979,32 +2930,60 @@ SlruScanDirCbFindEarliest(SlruCtl ctl, char *filename, int segpage, void *data)
  * and kept up to date as new pages are zeroed.
  */
 void
-TruncateMultiXact(void)
+TruncateMultiXact(MultiXactId frozenMulti, Oid minmulti_datoid, bool in_recovery)
 {
 	MultiXactId oldestMXact;
 	MultiXactOffset oldestOffset;
-	MultiXactId		nextMXact;
-	MultiXactOffset	nextOffset;
+	MultiXactId nextMXact;
+	MultiXactOffset nextOffset;
+	MultiXactOffset oldestAliveOffset;
 	mxtruncinfo trunc;
 	MultiXactId earliest;
-	MembersLiveRange range;
 
-	Assert(AmCheckpointerProcess() || AmStartupProcess() ||
-		   !IsPostmasterEnvironment);
+	/*
+	 * Need to allow being called in recovery for backward compatibility, when
+	 * a updated standby replays WAL generated by a non-updated primary.
+	 */
+	Assert(in_recovery || !RecoveryInProgress());
+	Assert(!in_recovery || AmStartupProcess());
+	Assert(in_recovery || MultiXactState->finishedStartup);
+
+	/*
+	 * We can only allow one truncation to happen at once. Otherwise parts of
+	 * members might vanish while we're doing lookups or similar. There's no
+	 * need to have an interlock with creating new multis or such, since those
+	 * are constrained by the limits (which only grow, never shrink).
+	 */
+	LWLockAcquire(MultiXactTruncationLock, LW_EXCLUSIVE);
 
 	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	oldestMXact = MultiXactState->lastCheckpointedOldest;
 	nextMXact = MultiXactState->nextMXact;
 	nextOffset = MultiXactState->nextOffset;
+	oldestMXact = MultiXactState->oldestMultiXactId;
 	LWLockRelease(MultiXactGenLock);
 	Assert(MultiXactIdIsValid(oldestMXact));
 
 	/*
+	 * Make sure to only attempt truncation if there's values to truncate
+	 * away. In normal processing values shouldn't go backwards, but there's
+	 * some corner cases (due to bugs) where that's possible.
+	 */
+	if (MultiXactIdPrecedesOrEquals(frozenMulti, oldestMXact))
+	{
+		LWLockRelease(MultiXactTruncationLock);
+		return;
+	}
+
+	/*
 	 * Note we can't just plow ahead with the truncation; it's possible that
 	 * there are no segments to truncate, which is a problem because we are
 	 * going to attempt to read the offsets page to determine where to
 	 * truncate the members SLRU.  So we first scan the directory to determine
 	 * the earliest offsets page number that we can read without error.
+	 *
+	 * XXX: It's also possible that the page that oldestMXact is on has
+	 * already been truncated away, and we crashed before updating
+	 * oldestMXact.
 	 */
 	trunc.earliestExistingPage = -1;
 	SlruScanDirectory(MultiXactOffsetCtl, SlruScanDirCbFindEarliest, &trunc);
@@ -3012,19 +2991,10 @@ TruncateMultiXact(void)
 	if (earliest < FirstMultiXactId)
 		earliest = FirstMultiXactId;
 
-	/*
-	 * If there's nothing to remove, we can bail out early.
-	 *
-	 * Due to bugs in early releases of PostgreSQL 9.3.X and 9.4.X,
-	 * oldestMXact might point to a multixact that does not exist.
-	 * Autovacuum will eventually advance it to a value that does exist,
-	 * and we want to set a proper offsetStopLimit when that happens,
-	 * so call DetermineSafeOldestOffset here even if we're not actually
-	 * truncating.
-	 */
+	/* If there's nothing to remove, we can bail out early. */
 	if (MultiXactIdPrecedes(oldestMXact, earliest))
 	{
-		DetermineSafeOldestOffset(oldestMXact);
+		LWLockRelease(MultiXactTruncationLock);
 		return;
 	}
 
@@ -3042,35 +3012,89 @@ TruncateMultiXact(void)
 	{
 		ereport(LOG,
 				(errmsg("oldest MultiXact %u not found, earliest MultiXact %u, skipping truncation",
-					oldestMXact, earliest)));
+						oldestMXact, earliest)));
+		LWLockRelease(MultiXactTruncationLock);
 		return;
 	}
 
 	/*
-	 * To truncate MultiXactMembers, we need to figure out the active page
-	 * range and delete all files outside that range.  The start point is the
-	 * start of the segment containing the oldest offset; an end point of the
-	 * segment containing the next offset to use is enough.  The end point is
-	 * updated as MultiXactMember gets extended concurrently, elsewhere.
+	 * Secondly compute up to where to truncate. Lookup the corresponding
+	 * member offset for frozenMulti for that.
 	 */
-	range.rangeStart = MXOffsetToMemberPage(oldestOffset);
-	range.rangeStart -= range.rangeStart % SLRU_PAGES_PER_SEGMENT;
+	if (frozenMulti == nextMXact)
+		oldestAliveOffset = nextOffset; /* there are NO MultiXacts */
+	else if (!find_multixact_start(frozenMulti, &oldestAliveOffset))
+	{
+		ereport(LOG,
+				(errmsg("supposedly still alive MultiXact %u not found, skipping truncation",
+						frozenMulti)));
+		LWLockRelease(MultiXactTruncationLock);
+		return;
+	}
 
-	range.rangeEnd = MXOffsetToMemberPage(nextOffset);
+	elog(DEBUG1, "performing multixact truncation: offsets [%u, %u),  members [%u, %u), member segments [%x to %x)",
+		 oldestMXact, frozenMulti,
+		 oldestOffset,
+		 oldestAliveOffset,
+		 MXOffsetToMemberSegment(oldestOffset),
+		 MXOffsetToMemberSegment(oldestAliveOffset));
 
-	SlruScanDirectory(MultiXactMemberCtl, SlruScanDirCbRemoveMembers, &range);
+	/*
+	 * Do truncation, and the WAL logging of the truncation, in a critical
+	 * section. That way offsets/members cannot get out of sync anymore, i.e.
+	 * once consistent the oldestMulti will always exist in members, even if
+	 * we crashed in the wrong moment.
+	 */
+	START_CRIT_SECTION();
 
-	/* Now we can truncate MultiXactOffset */
-	SimpleLruTruncate(MultiXactOffsetCtl,
-					  MultiXactIdToOffsetPage(oldestMXact));
+	/*
+	 * Prevent checkpoints from being scheduled concurrently. This is critical
+	 * because otherwise a truncation record might not be replayed after a
+	 * crash/basebackup, even though the state of the data directory would
+	 * require it.  It's not possible, and not needed, to do this during
+	 * recovery, when performing a old-style truncation, though, as the
+	 * startup process doesn't have a PGXACT entry.
+	 */
+	if (!in_recovery)
+	{
+		Assert(!MyPgXact->delayChkpt);
+		MyPgXact->delayChkpt = true;
+	}
 
+	/*
+	 * Wal log truncation - this has to be flushed before the truncation is
+	 * actually performed, for the reasons explained in TruncateCLOG().
+	 */
+	if (!in_recovery)
+		WriteMTruncateXlogRec(minmulti_datoid,
+							  oldestMXact, frozenMulti,
+							  oldestOffset, oldestAliveOffset);
 
 	/*
-	 * Now, and only now, we can advance the stop point for multixact members.
-	 * If we did it any sooner, the segments we deleted above might already
-	 * have been overwritten with new members.  That would be bad.
+	 * Update in-memory limits before performing the truncation, while inside
+	 * the critical section: Have to do it before truncation, to prevent
+	 * concurrent lookups of those values. Has to be inside the critical
+	 * section asotherwise a future call to this function would error out,
+	 * while looking up the oldest member in offsets, if our caller crashes
+	 * before updating the limits.
 	 */
-	DetermineSafeOldestOffset(oldestMXact);
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	MultiXactState->oldestMultiXactId = frozenMulti;
+	MultiXactState->oldestMultiXactDB = minmulti_datoid;
+	LWLockRelease(MultiXactGenLock);
+
+	/* First truncate members */
+	PerformMembersTruncation(oldestOffset, oldestAliveOffset);
+
+	/* Then offsets */
+	SimpleLruTruncate(MultiXactOffsetCtl,
+					  MultiXactIdToOffsetPage(frozenMulti));
+
+	if (!in_recovery)
+		MyPgXact->delayChkpt = false;
+
+	END_CRIT_SECTION();
+	LWLockRelease(MultiXactTruncationLock);
 }
 
 /*
@@ -3167,6 +3191,34 @@ WriteMZeroPageXlogRec(int pageno, uint8 info)
 }
 
 /*
+ * Write a TRUNCATE xlog record
+ *
+ * We must flush the xlog record to disk before returning --- see notes
+ * in TruncateMultiXact().
+ */
+static void
+WriteMTruncateXlogRec(Oid oldestMultiDB,
+					  MultiXactId startTruncOff, MultiXactId endTruncOff,
+				MultiXactOffset startTruncMemb, MultiXactOffset endTruncMemb)
+{
+	XLogRecPtr	recptr;
+	xl_multixact_truncate xlrec;
+
+	xlrec.oldestMultiDB = oldestMultiDB;
+
+	xlrec.startTruncOff = startTruncOff;
+	xlrec.endTruncOff = endTruncOff;
+
+	xlrec.startTruncMemb = startTruncMemb;
+	xlrec.endTruncMemb = endTruncMemb;
+
+	XLogBeginInsert();
+	XLogRegisterData((char *) (&xlrec), SizeOfMultiXactTruncate);
+	recptr = XLogInsert(RM_MULTIXACT_ID, XLOG_MULTIXACT_TRUNCATE_ID);
+	XLogFlush(recptr);
+}
+
+/*
  * MULTIXACT resource manager's routines
  */
 void
@@ -3248,6 +3300,47 @@ multixact_redo(XLogReaderState *record)
 			LWLockRelease(XidGenLock);
 		}
 	}
+	else if (info == XLOG_MULTIXACT_TRUNCATE_ID)
+	{
+		xl_multixact_truncate xlrec;
+		int			pageno;
+
+		memcpy(&xlrec, XLogRecGetData(record),
+			   SizeOfMultiXactTruncate);
+
+		pageno = MultiXactIdToOffsetPage(xlrec.endTruncOff);
+
+		elog(LOG, "replaying multixact truncation start: %u, %u, %x to %x",
+			 xlrec.startTruncMemb,
+			 xlrec.endTruncMemb,
+			 MXOffsetToMemberSegment(xlrec.startTruncMemb),
+			 MXOffsetToMemberSegment(xlrec.endTruncMemb));
+
+		/*
+		 * Advance the horizon values, so they're current at the end of
+		 * recovery.
+		 */
+		SetMultiXactIdLimit(xlrec.endTruncOff, xlrec.oldestMultiDB);
+
+		/* should not be required, but more than cheap enough */
+		LWLockAcquire(MultiXactTruncationLock, LW_EXCLUSIVE);
+
+		PerformMembersTruncation(xlrec.startTruncMemb, xlrec.endTruncMemb);
+
+		/*
+		 * During XLOG replay, latest_page_number isn't necessarily set up
+		 * yet; insert a suitable value to bypass the sanity test in
+		 * SimpleLruTruncate.
+		 */
+		MultiXactOffsetCtl->shared->latest_page_number = pageno;
+		SimpleLruTruncate(MultiXactOffsetCtl,
+						  MultiXactIdToOffsetPage(xlrec.endTruncOff));
+
+		LWLockRelease(MultiXactTruncationLock);
+
+		/* only looked at in the startup process, no lock necessary */
+		MultiXactState->sawTruncationCkptCycle = true;
+	}
 	else
 		elog(PANIC, "multixact_redo: unknown op code %u", info);
 }
diff --git a/src/backend/access/transam/slru.c b/src/backend/access/transam/slru.c
index 5fcea11..90c7cf5 100644
--- a/src/backend/access/transam/slru.c
+++ b/src/backend/access/transam/slru.c
@@ -134,6 +134,7 @@ static int	SlruSelectLRUPage(SlruCtl ctl, int pageno);
 
 static bool SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename,
 						  int segpage, void *data);
+static void SlruInternalDeleteSegment(SlruCtl ctl, char *filename);
 
 /*
  * Initialization of shared memory
@@ -1075,7 +1076,7 @@ SlruSelectLRUPage(SlruCtl ctl, int pageno)
  * Flush dirty pages to disk during checkpoint or database shutdown
  */
 void
-SimpleLruFlush(SlruCtl ctl, bool checkpoint)
+SimpleLruFlush(SlruCtl ctl, bool allow_redirtied)
 {
 	SlruShared	shared = ctl->shared;
 	SlruFlushData fdata;
@@ -1096,11 +1097,11 @@ SimpleLruFlush(SlruCtl ctl, bool checkpoint)
 		SlruInternalWritePage(ctl, slotno, &fdata);
 
 		/*
-		 * When called during a checkpoint, we cannot assert that the slot is
-		 * clean now, since another process might have re-dirtied it already.
-		 * That's okay.
+		 * In some places (e.g. checkpoints), we cannot assert that the slot
+		 * is clean now, since another process might have re-dirtied it
+		 * already.  That's okay.
 		 */
-		Assert(checkpoint ||
+		Assert(allow_redirtied ||
 			   shared->page_status[slotno] == SLRU_PAGE_EMPTY ||
 			   (shared->page_status[slotno] == SLRU_PAGE_VALID &&
 				!shared->page_dirty[slotno]));
@@ -1210,8 +1211,14 @@ restart:;
 	(void) SlruScanDirectory(ctl, SlruScanDirCbDeleteCutoff, &cutoffPage);
 }
 
-void
-SlruDeleteSegment(SlruCtl ctl, char *filename)
+/*
+ * Delete an individual SLRU segment, identified by the filename.
+ *
+ * NB: This does not touch the SLRU buffers themselves, callers have to ensure
+ * they either can't yet contain anything, or have already been cleaned out.
+ */
+static void
+SlruInternalDeleteSegment(SlruCtl ctl, char *filename)
 {
 	char		path[MAXPGPATH];
 
@@ -1222,6 +1229,64 @@ SlruDeleteSegment(SlruCtl ctl, char *filename)
 }
 
 /*
+ * Delete an individual SLRU segment, identified by the segment number.
+ */
+void
+SlruDeleteSegment(SlruCtl ctl, int segno)
+{
+	SlruShared	shared = ctl->shared;
+	int			slotno;
+	char		path[MAXPGPATH];
+	bool		did_write;
+
+	/* Clean out any possibly existing references to the segment. */
+	LWLockAcquire(shared->ControlLock, LW_EXCLUSIVE);
+restart:
+	did_write = false;
+	for (slotno = 0; slotno < shared->num_slots; slotno++)
+	{
+		int			pagesegno = shared->page_number[slotno] / SLRU_PAGES_PER_SEGMENT;
+
+		if (shared->page_status[slotno] == SLRU_PAGE_EMPTY)
+			continue;
+
+		/* not the segment we're looking for */
+		if (pagesegno != segno)
+			continue;
+
+		/* If page is clean, just change state to EMPTY (expected case). */
+		if (shared->page_status[slotno] == SLRU_PAGE_VALID &&
+			!shared->page_dirty[slotno])
+		{
+			shared->page_status[slotno] = SLRU_PAGE_EMPTY;
+			continue;
+		}
+
+		/* Same logic as SimpleLruTruncate() */
+		if (shared->page_status[slotno] == SLRU_PAGE_VALID)
+			SlruInternalWritePage(ctl, slotno, NULL);
+		else
+			SimpleLruWaitIO(ctl, slotno);
+
+		did_write = true;
+	}
+
+	/*
+	 * Be extra careful and re-check. The IO functions release the control
+	 * lock, so new pages could have been read in.
+	 */
+	if (did_write)
+		goto restart;
+
+	snprintf(path, MAXPGPATH, "%s/%04X", ctl->Dir, segno);
+	ereport(DEBUG2,
+			(errmsg("removing file \"%s\"", path)));
+	unlink(path);
+
+	LWLockRelease(shared->ControlLock);
+}
+
+/*
  * SlruScanDirectory callback
  *		This callback reports true if there's any segment prior to the one
  *		containing the page passed as "data".
@@ -1249,7 +1314,7 @@ SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename, int segpage, void *data)
 	int			cutoffPage = *(int *) data;
 
 	if (ctl->PagePrecedes(segpage, cutoffPage))
-		SlruDeleteSegment(ctl, filename);
+		SlruInternalDeleteSegment(ctl, filename);
 
 	return false;				/* keep going */
 }
@@ -1261,7 +1326,7 @@ SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename, int segpage, void *data)
 bool
 SlruScanDirCbDeleteAll(SlruCtl ctl, char *filename, int segpage, void *data)
 {
-	SlruDeleteSegment(ctl, filename);
+	SlruInternalDeleteSegment(ctl, filename);
 
 	return false;				/* keep going */
 }
diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index 4e37ad3..541cd3b 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -6287,7 +6287,6 @@ StartupXLOG(void)
 	SetMultiXactIdLimit(checkPoint.oldestMulti, checkPoint.oldestMultiDB);
 	SetCommitTsLimit(checkPoint.oldestCommitTs,
 					 checkPoint.newestCommitTs);
-	MultiXactSetSafeTruncate(checkPoint.oldestMulti);
 	XLogCtl->ckptXidEpoch = checkPoint.nextXidEpoch;
 	XLogCtl->ckptXid = checkPoint.nextXid;
 
@@ -6304,10 +6303,8 @@ StartupXLOG(void)
 	StartupReorderBuffer();
 
 	/*
-	 * Startup MultiXact.  We need to do this early for two reasons: one is
-	 * that we might try to access multixacts when we do tuple freezing, and
-	 * the other is we need its state initialized because we attempt
-	 * truncation during restartpoints.
+	 * Startup MultiXact, we need to do this early, to be able to replay
+	 * truncations.
 	 */
 	StartupMultiXact();
 
@@ -8465,12 +8462,6 @@ CreateCheckPoint(int flags)
 	END_CRIT_SECTION();
 
 	/*
-	 * Now that the checkpoint is safely on disk, we can update the point to
-	 * which multixact can be truncated.
-	 */
-	MultiXactSetSafeTruncate(checkPoint.oldestMulti);
-
-	/*
 	 * Let smgr do post-checkpoint cleanup (eg, deleting old files).
 	 */
 	smgrpostckpt();
@@ -8509,11 +8500,6 @@ CreateCheckPoint(int flags)
 	if (!RecoveryInProgress())
 		TruncateSUBTRANS(GetOldestXmin(NULL, false));
 
-	/*
-	 * Truncate pg_multixact too.
-	 */
-	TruncateMultiXact();
-
 	/* Real work is done, but log and update stats before releasing lock. */
 	LogCheckpointEnd(false);
 
@@ -8844,21 +8830,6 @@ CreateRestartPoint(int flags)
 	}
 
 	/*
-	 * Due to a historical accident multixact truncations are not WAL-logged,
-	 * but just performed everytime the mxact horizon is increased. So, unless
-	 * we explicitly execute truncations on a standby it will never clean out
-	 * /pg_multixact which obviously is bad, both because it uses space and
-	 * because we can wrap around into pre-existing data...
-	 *
-	 * We can only do the truncation here, after the UpdateControlFile()
-	 * above, because we've now safely established a restart point.  That
-	 * guarantees we will not need to access those multis.
-	 *
-	 * It's probably worth improving this.
-	 */
-	TruncateMultiXact();
-
-	/*
 	 * Truncate pg_subtrans if possible.  We can throw away all data before
 	 * the oldest XMIN of any running transaction.  No future transaction will
 	 * attempt to reference any pg_subtrans entry older than that (see Asserts
@@ -9218,9 +9189,14 @@ xlog_redo(XLogReaderState *record)
 		LWLockRelease(OidGenLock);
 		MultiXactSetNextMXact(checkPoint.nextMulti,
 							  checkPoint.nextMultiOffset);
+
+		/*
+		 * NB: This may perform multixact truncation when replaying WAL
+		 * generated by an older primary.
+		 */
+		MultiXactAdvanceOldest(checkPoint.oldestMulti,
+							   checkPoint.oldestMultiDB);
 		SetTransactionIdLimit(checkPoint.oldestXid, checkPoint.oldestXidDB);
-		SetMultiXactIdLimit(checkPoint.oldestMulti, checkPoint.oldestMultiDB);
-		MultiXactSetSafeTruncate(checkPoint.oldestMulti);
 
 		/*
 		 * If we see a shutdown checkpoint while waiting for an end-of-backup
@@ -9310,14 +9286,17 @@ xlog_redo(XLogReaderState *record)
 		LWLockRelease(OidGenLock);
 		MultiXactAdvanceNextMXact(checkPoint.nextMulti,
 								  checkPoint.nextMultiOffset);
+
+		/*
+		 * NB: This may perform multixact truncation when replaying WAL
+		 * generated by an older primary.
+		 */
+		MultiXactAdvanceOldest(checkPoint.oldestMulti,
+							   checkPoint.oldestMultiDB);
 		if (TransactionIdPrecedes(ShmemVariableCache->oldestXid,
 								  checkPoint.oldestXid))
 			SetTransactionIdLimit(checkPoint.oldestXid,
 								  checkPoint.oldestXidDB);
-		MultiXactAdvanceOldest(checkPoint.oldestMulti,
-							   checkPoint.oldestMultiDB);
-		MultiXactSetSafeTruncate(checkPoint.oldestMulti);
-
 		/* ControlFile->checkPointCopy always tracks the latest ckpt XID */
 		ControlFile->checkPointCopy.nextXidEpoch = checkPoint.nextXidEpoch;
 		ControlFile->checkPointCopy.nextXid = checkPoint.nextXid;
diff --git a/src/backend/commands/vacuum.c b/src/backend/commands/vacuum.c
index baf66f1..c1433e9 100644
--- a/src/backend/commands/vacuum.c
+++ b/src/backend/commands/vacuum.c
@@ -1134,11 +1134,11 @@ vac_truncate_clog(TransactionId frozenXID,
 		return;
 
 	/*
-	 * Truncate CLOG and CommitTs to the oldest computed value. Note we don't
-	 * truncate multixacts; that will be done by the next checkpoint.
+	 * Truncate CLOG, multixact and CommitTs to the oldest computed value.
 	 */
 	TruncateCLOG(frozenXID);
 	TruncateCommitTs(frozenXID, true);
+	TruncateMultiXact(minMulti, minmulti_datoid, false);
 
 	/*
 	 * Update the wrap limit for GetNewTransactionId and creation of new
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index 6213f8a..7817546 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -71,6 +71,7 @@ typedef struct MultiXactMember
 #define XLOG_MULTIXACT_ZERO_OFF_PAGE	0x00
 #define XLOG_MULTIXACT_ZERO_MEM_PAGE	0x10
 #define XLOG_MULTIXACT_CREATE_ID		0x20
+#define XLOG_MULTIXACT_TRUNCATE_ID		0x30
 
 typedef struct xl_multixact_create
 {
@@ -82,6 +83,20 @@ typedef struct xl_multixact_create
 
 #define SizeOfMultiXactCreate (offsetof(xl_multixact_create, members))
 
+typedef struct xl_multixact_truncate
+{
+	Oid			oldestMultiDB;
+
+	/* to-be-truncated range of multixact offsets */
+	MultiXactId startTruncOff;	/* just for completeness' sake */
+	MultiXactId endTruncOff;
+
+	/* to-be-truncated range of multixact members */
+	MultiXactOffset startTruncMemb;
+	MultiXactOffset endTruncMemb;
+} xl_multixact_truncate;
+#define SizeOfMultiXactTruncate (sizeof(xl_multixact_truncate))
+
 
 extern MultiXactId MultiXactIdCreate(TransactionId xid1,
 				  MultiXactStatus status1, TransactionId xid2,
@@ -120,13 +135,12 @@ extern void MultiXactGetCheckptMulti(bool is_shutdown,
 						 Oid *oldestMultiDB);
 extern void CheckPointMultiXact(void);
 extern MultiXactId GetOldestMultiXactId(void);
-extern void TruncateMultiXact(void);
+extern void TruncateMultiXact(MultiXactId oldestMulti, Oid oldestMultiDB, bool inRecovery);
 extern void MultiXactSetNextMXact(MultiXactId nextMulti,
 					  MultiXactOffset nextMultiOffset);
 extern void MultiXactAdvanceNextMXact(MultiXactId minMulti,
 						  MultiXactOffset minMultiOffset);
 extern void MultiXactAdvanceOldest(MultiXactId oldestMulti, Oid oldestMultiDB);
-extern void MultiXactSetSafeTruncate(MultiXactId safeTruncateMulti);
 extern int	MultiXactMemberFreezeThreshold(void);
 
 extern void multixact_twophase_recover(TransactionId xid, uint16 info,
diff --git a/src/include/access/slru.h b/src/include/access/slru.h
index 9c7f019..f60e75b 100644
--- a/src/include/access/slru.h
+++ b/src/include/access/slru.h
@@ -143,14 +143,14 @@ extern int SimpleLruReadPage(SlruCtl ctl, int pageno, bool write_ok,
 extern int SimpleLruReadPage_ReadOnly(SlruCtl ctl, int pageno,
 						   TransactionId xid);
 extern void SimpleLruWritePage(SlruCtl ctl, int slotno);
-extern void SimpleLruFlush(SlruCtl ctl, bool checkpoint);
+extern void SimpleLruFlush(SlruCtl ctl, bool allow_redirtied);
 extern void SimpleLruTruncate(SlruCtl ctl, int cutoffPage);
 extern bool SimpleLruDoesPhysicalPageExist(SlruCtl ctl, int pageno);
 
 typedef bool (*SlruScanCallback) (SlruCtl ctl, char *filename, int segpage,
 											  void *data);
 extern bool SlruScanDirectory(SlruCtl ctl, SlruScanCallback callback, void *data);
-extern void SlruDeleteSegment(SlruCtl ctl, char *filename);
+extern void SlruDeleteSegment(SlruCtl ctl, int segno);
 
 /* SlruScanDirectory public callbacks */
 extern bool SlruScanDirCbReportPresence(SlruCtl ctl, char *filename,
diff --git a/src/include/storage/lwlock.h b/src/include/storage/lwlock.h
index cff3b99..6f0688c 100644
--- a/src/include/storage/lwlock.h
+++ b/src/include/storage/lwlock.h
@@ -135,8 +135,9 @@ extern PGDLLIMPORT LWLockPadded *MainLWLockArray;
 #define CommitTsControlLock			(&MainLWLockArray[38].lock)
 #define CommitTsLock				(&MainLWLockArray[39].lock)
 #define ReplicationOriginLock		(&MainLWLockArray[40].lock)
+#define MultiXactTruncationLock		(&MainLWLockArray[41].lock)
 
-#define NUM_INDIVIDUAL_LWLOCKS		41
+#define NUM_INDIVIDUAL_LWLOCKS		42
 
 /*
  * It's a bit odd to declare NUM_BUFFER_PARTITIONS and NUM_LOCK_PARTITIONS
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 4b650d1..23ba334 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2749,6 +2749,7 @@ xl_invalid_page
 xl_invalid_page_key
 xl_multi_insert_tuple
 xl_multixact_create
+xl_multixact_truncate
 xl_parameter_change
 xl_relmap_update
 xl_replorigin_drop
-- 
2.4.0.rc2.1.g3d6bc9a

>From b4a6fade2dc06c4658dbfd1bf1801b30d5c3e388 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Thu, 4 Jun 2015 19:38:32 +0200
Subject: [PATCH 1/3] WIP-dontcommit: Add functions to burn multixacts

This should live in its own module, but we don't have that yet.
---
 contrib/pageinspect/heapfuncs.c          | 43 ++++++++++++++++++++++++++++++++
 contrib/pageinspect/pageinspect--1.3.sql |  6 +++++
 src/backend/access/heap/heapam.c         |  2 +-
 src/backend/access/transam/multixact.c   | 15 ++++++-----
 src/include/access/multixact.h           |  3 ++-
 5 files changed, 61 insertions(+), 8 deletions(-)

diff --git a/contrib/pageinspect/heapfuncs.c b/contrib/pageinspect/heapfuncs.c
index 8d1666c..7a3aa14 100644
--- a/contrib/pageinspect/heapfuncs.c
+++ b/contrib/pageinspect/heapfuncs.c
@@ -29,6 +29,8 @@
 #include "funcapi.h"
 #include "utils/builtins.h"
 #include "miscadmin.h"
+#include "access/multixact.h"
+#include "access/transam.h"
 
 
 /*
@@ -223,3 +225,44 @@ heap_page_items(PG_FUNCTION_ARGS)
 	else
 		SRF_RETURN_DONE(fctx);
 }
+
+extern Datum
+pg_burn_multixact(PG_FUNCTION_ARGS);
+PG_FUNCTION_INFO_V1(pg_burn_multixact);
+
+Datum
+pg_burn_multixact(PG_FUNCTION_ARGS)
+{
+	int		rep = PG_GETARG_INT32(0);
+	int		size = PG_GETARG_INT32(1);
+	MultiXactMember *members;
+	MultiXactId ret;
+	TransactionId id = ReadNewTransactionId() - size;
+	int		i;
+
+	if (rep < 1)
+		elog(ERROR, "need to burn, burn, burn");
+
+	members = palloc(size * sizeof(MultiXactMember));
+	for (i = 0; i < size; i++)
+	{
+		members[i].xid = id++;
+		members[i].status = MultiXactStatusForShare;
+
+		if (!TransactionIdIsNormal(members[i].xid))
+		{
+			id = FirstNormalTransactionId;
+			members[i].xid = id++;
+		}
+	}
+
+	MultiXactIdSetOldestMember();
+
+	for (i = 0; i < rep; i++)
+	{
+		CHECK_FOR_INTERRUPTS();
+		ret = MultiXactIdCreateFromMembers(size, members, true);
+	}
+
+	PG_RETURN_INT64((int64) ret);
+}
diff --git a/contrib/pageinspect/pageinspect--1.3.sql b/contrib/pageinspect/pageinspect--1.3.sql
index a99e058..22f51bc 100644
--- a/contrib/pageinspect/pageinspect--1.3.sql
+++ b/contrib/pageinspect/pageinspect--1.3.sql
@@ -187,3 +187,9 @@ CREATE FUNCTION gin_leafpage_items(IN page bytea,
 RETURNS SETOF record
 AS 'MODULE_PATHNAME', 'gin_leafpage_items'
 LANGUAGE C STRICT;
+
+
+CREATE FUNCTION pg_burn_multixact(num int4, size int4)
+RETURNS int4
+AS 'MODULE_PATHNAME', 'pg_burn_multixact'
+LANGUAGE C STRICT;
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index bcf9871..e167684 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -6099,7 +6099,7 @@ FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
 		 * Create a new multixact with the surviving members of the previous
 		 * one, to set as new Xmax in the tuple.
 		 */
-		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers);
+		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers, false);
 		*flags |= FRM_RETURN_IS_MULTI;
 	}
 
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 1933a87..34c5370 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -407,7 +407,7 @@ MultiXactIdCreate(TransactionId xid1, MultiXactStatus status1,
 	members[1].xid = xid2;
 	members[1].status = status2;
 
-	newMulti = MultiXactIdCreateFromMembers(2, members);
+	newMulti = MultiXactIdCreateFromMembers(2, members, false);
 
 	debug_elog3(DEBUG2, "Create: %s",
 				mxid_to_string(newMulti, 2, members));
@@ -473,7 +473,7 @@ MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
 		 */
 		member.xid = xid;
 		member.status = status;
-		newMulti = MultiXactIdCreateFromMembers(1, &member);
+		newMulti = MultiXactIdCreateFromMembers(1, &member, false);
 
 		debug_elog4(DEBUG2, "Expand: %u has no members, create singleton %u",
 					multi, newMulti);
@@ -525,7 +525,7 @@ MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
 
 	newMembers[j].xid = xid;
 	newMembers[j++].status = status;
-	newMulti = MultiXactIdCreateFromMembers(j, newMembers);
+	newMulti = MultiXactIdCreateFromMembers(j, newMembers, false);
 
 	pfree(members);
 	pfree(newMembers);
@@ -744,7 +744,7 @@ ReadNextMultiXactId(void)
  * NB: the passed members[] array will be sorted in-place.
  */
 MultiXactId
-MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
+MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members, bool nocache)
 {
 	MultiXactId multi;
 	MultiXactOffset offset;
@@ -763,7 +763,9 @@ MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
 	 * corner cases where someone else added us to a MultiXact without our
 	 * knowledge, but it's not worth checking for.)
 	 */
-	multi = mXactCacheGetBySet(nmembers, members);
+	multi = nocache ? InvalidMultiXactId :
+		mXactCacheGetBySet(nmembers, members);
+
 	if (MultiXactIdIsValid(multi))
 	{
 		debug_elog2(DEBUG2, "Create: in cache!");
@@ -836,7 +838,8 @@ MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
 	END_CRIT_SECTION();
 
 	/* Store the new MultiXactId in the local cache, too */
-	mXactCachePut(multi, nmembers, members);
+	if (!nocache)
+		mXactCachePut(multi, nmembers, members);
 
 	debug_elog2(DEBUG2, "Create: all done");
 
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index f1448fe..6213f8a 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -86,10 +86,11 @@ typedef struct xl_multixact_create
 extern MultiXactId MultiXactIdCreate(TransactionId xid1,
 				  MultiXactStatus status1, TransactionId xid2,
 				  MultiXactStatus status2);
+extern MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members, bool nocache);
 extern MultiXactId MultiXactIdExpand(MultiXactId multi, TransactionId xid,
 				  MultiXactStatus status);
 extern MultiXactId MultiXactIdCreateFromMembers(int nmembers,
-							 MultiXactMember *members);
+							 MultiXactMember *members, bool nocache);
 
 extern MultiXactId ReadNextMultiXactId(void);
 extern bool MultiXactIdIsRunning(MultiXactId multi, bool isLockOnly);
-- 
2.5.0.400.gff86faf

>From a7b0af940ecb1140deee3582508fc0a2dd64e03b Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Mon, 15 Jun 2015 19:12:52 +0200
Subject: [PATCH 2/3] Lower *_freeze_max_age minimum values.

The old minimum values are rather large, making it time consuming to
test related behaviour. Additionally the current limits, especially for
multixacts, can be problematic in space-constrained systems. 10000000
multixacts can contain a lot of members.

Since there's no good reason for the current limits, lower them a good
bit. Setting them to 0 would be a bad idea, triggering endless vacuums,
so still retain a limit.

While at it fix autovacuum_multixact_freeze_max_age to refer to
multixact.c instead of varsup.c.

Reviewed-By: Robert Haas
Discussion: CA+TgmoYmQPHcrc3GSs7vwvrbTkbcGD9Gik=OztbDGGrovkkEzQ@mail.gmail.com
Backpatch: back to 9.0 (in parts)
---
 src/backend/utils/misc/guc.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index fcba3c5..17053af 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -2510,17 +2510,17 @@ static struct config_int ConfigureNamesInt[] =
 		},
 		&autovacuum_freeze_max_age,
 		/* see pg_resetxlog if you change the upper-limit value */
-		200000000, 100000000, 2000000000,
+		200000000, 100000, 2000000000,
 		NULL, NULL, NULL
 	},
 	{
-		/* see varsup.c for why this is PGC_POSTMASTER not PGC_SIGHUP */
+		/* see multixact.c for why this is PGC_POSTMASTER not PGC_SIGHUP */
 		{"autovacuum_multixact_freeze_max_age", PGC_POSTMASTER, AUTOVACUUM,
 			gettext_noop("Multixact age at which to autovacuum a table to prevent multixact wraparound."),
 			NULL
 		},
 		&autovacuum_multixact_freeze_max_age,
-		400000000, 10000000, 2000000000,
+		400000000, 10000, 2000000000,
 		NULL, NULL, NULL
 	},
 	{
-- 
2.5.0.400.gff86faf

>From 7d83bd78b7ca0bad52a6d54a996b8fe8c15b4f65 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Tue, 22 Sep 2015 15:17:09 +0200
Subject: [PATCH 3/3] Rework the way multixact truncations work.

The fact that multixact truncations are not WAL logged has caused a fair
share of problems. Amongst others it requires to do computations during
recovery while the database is not in a consistent state, delaying
truncations till checkpoints, and handling members being truncated, but
offset not.

We tried to put bandaids on lots of these issues over the last years,
but it seems time to change course. Thus this patch introduces WAL
logging for truncation, even in the back branches.

This allows:
1) to perform the truncation directly during VACUUM, instead of delaying it
   to the checkpoint.
2) to avoid looking at the offsets SLRU for truncation during recovery,
   we can just use the master's values.
3) simplify a fair amount of logic to keep in memory limits straight,
   this has gotten much easier

During the course of fixing this a bunch of bugs had to be fixed:
1) Data was not purged from memory the member's slru before deleting
   segments. This happend to be hard or impossible to hit due to the
   interlock between checkpoints and truncation.
2) find_multixact_start() relied on SimpleLruDoesPhysicalPageExist - but
   that doesn't work for offsets that haven't yet been flushed to
   disk. Flush out before running to fix. Not pretty, but it feels
   slightly safer to only make decisions based on on-disk state.
3) find_multixact_start() could be called concurrently with a truncation
   and thus fail. Via SetOffsetVacuumLimit() that could lead to a round
   of emergency vacuuming. The problem remains in
   pg_get_multixact_members(), but that's quite harmless.

To handle the case of an updated standby replaying WAL from a not-yet
upgraded primary we have to recognize that situation and use "old style"
truncation (i.e. looking at the SLRUs) during WAL replay. In contrast to
before this now happens in the startup process, when replaying a
checkpoint record, instead of the checkpointer. Doing this in the
restartpoint was incorrect, they can happen much later than the original
checkpoint, thereby leading to wraparound. It's also more in line to how
the WAL logging now works.

To avoid "multixact_redo: unknown op code 48" errors standbys should be
upgraded before primaries. This needs to be expressed clearly in the
release notes.

Backpatch to 9.3, where the use of multixacts was expanded. Arguably
this could be backpatched further, but there doesn't seem to be
sufficient benefit to outweigh the risk of applying a significantly
different patch there.

Discussion: 20150621192409.GA4797@alap3.anarazel.de
Reviewed-By: Robert Haas, Alvaro Herrera, Thomas Munro
Backpatch: 9.3
---
 src/backend/access/rmgrdesc/mxactdesc.c  |  11 +
 src/backend/access/transam/multixact.c   | 651 ++++++++++++++++++-------------
 src/backend/access/transam/slru.c        |  83 +++-
 src/backend/access/transam/xlog.c        |  53 +--
 src/backend/commands/vacuum.c            |   4 +-
 src/backend/storage/lmgr/lwlocknames.txt |   1 +
 src/include/access/multixact.h           |  19 +-
 src/include/access/slru.h                |   4 +-
 src/tools/pgindent/typedefs.list         |   1 +
 9 files changed, 507 insertions(+), 320 deletions(-)

diff --git a/src/backend/access/rmgrdesc/mxactdesc.c b/src/backend/access/rmgrdesc/mxactdesc.c
index 572951e..5b8134f 100644
--- a/src/backend/access/rmgrdesc/mxactdesc.c
+++ b/src/backend/access/rmgrdesc/mxactdesc.c
@@ -70,6 +70,14 @@ multixact_desc(StringInfo buf, XLogReaderState *record)
 		for (i = 0; i < xlrec->nmembers; i++)
 			out_member(buf, &xlrec->members[i]);
 	}
+	else if (info == XLOG_MULTIXACT_TRUNCATE_ID)
+	{
+		xl_multixact_truncate *xlrec = (xl_multixact_truncate *) rec;
+
+		appendStringInfo(buf, "offsets [%u, %u), members [%u, %u)",
+						 xlrec->startTruncOff, xlrec->endTruncOff,
+						 xlrec->startTruncMemb, xlrec->endTruncMemb);
+	}
 }
 
 const char *
@@ -88,6 +96,9 @@ multixact_identify(uint8 info)
 		case XLOG_MULTIXACT_CREATE_ID:
 			id = "CREATE_ID";
 			break;
+		case XLOG_MULTIXACT_TRUNCATE_ID:
+			id = "TRUNCATE_ID";
+			break;
 	}
 
 	return id;
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 34c5370..1c3cfbe 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -49,9 +49,7 @@
  * value is removed; the cutoff value is stored in pg_class.  The minimum value
  * across all tables in each database is stored in pg_database, and the global
  * minimum across all databases is part of pg_control and is kept in shared
- * memory.  At checkpoint time, after the value is known flushed in WAL, any
- * files that correspond to multixacts older than that value are removed.
- * (These files are also removed when a restartpoint is executed.)
+ * memory.  Whenever that minimum is advanced, the SLRUs are truncated.
  *
  * When new multixactid values are to be created, care is taken that the
  * counter does not fall within the wraparound horizon considering the global
@@ -83,6 +81,7 @@
 #include "postmaster/autovacuum.h"
 #include "storage/lmgr.h"
 #include "storage/pmsignal.h"
+#include "storage/proc.h"
 #include "storage/procarray.h"
 #include "utils/builtins.h"
 #include "utils/memutils.h"
@@ -109,6 +108,7 @@
 	((xid) / (MultiXactOffset) MULTIXACT_OFFSETS_PER_PAGE)
 #define MultiXactIdToOffsetEntry(xid) \
 	((xid) % (MultiXactOffset) MULTIXACT_OFFSETS_PER_PAGE)
+#define MultiXactIdToOffsetSegment(xid) (MultiXactIdToOffsetPage(xid) / SLRU_PAGES_PER_SEGMENT)
 
 /*
  * The situation for members is a bit more complex: we store one byte of
@@ -153,6 +153,7 @@
 
 /* page in which a member is to be found */
 #define MXOffsetToMemberPage(xid) ((xid) / (TransactionId) MULTIXACT_MEMBERS_PER_PAGE)
+#define MXOffsetToMemberSegment(xid) (MXOffsetToMemberPage(xid) / SLRU_PAGES_PER_SEGMENT)
 
 /* Location (byte offset within page) of flag word for a given member */
 #define MXOffsetToFlagsOffset(xid) \
@@ -220,11 +221,12 @@ typedef struct MultiXactStateData
 	bool		oldestOffsetKnown;
 
 	/*
-	 * This is what the previous checkpoint stored as the truncate position.
-	 * This value is the oldestMultiXactId that was valid when a checkpoint
-	 * was last executed.
+	 * True if a multixact truncation WAL record was replayed since the last
+	 * checkpoint. This is used to trigger 'legacy truncations', i.e. truncate
+	 * by looking at the data directory during WAL replay, when the primary is
+	 * too old to generate truncation records.
 	 */
-	MultiXactId lastCheckpointedOldest;
+	bool		sawTruncationInCkptCycle;
 
 	/* support for anti-wraparound measures */
 	MultiXactId multiVacLimit;
@@ -233,8 +235,7 @@ typedef struct MultiXactStateData
 	MultiXactId multiWrapLimit;
 
 	/* support for members anti-wraparound measures */
-	MultiXactOffset offsetStopLimit;
-	bool offsetStopLimitKnown;
+	MultiXactOffset offsetStopLimit;	/* known if oldestOffsetKnown */
 
 	/*
 	 * Per-backend data starts here.  We have two arrays stored in the area
@@ -364,12 +365,14 @@ static bool MultiXactOffsetPrecedes(MultiXactOffset offset1,
 						MultiXactOffset offset2);
 static void ExtendMultiXactOffset(MultiXactId multi);
 static void ExtendMultiXactMember(MultiXactOffset offset, int nmembers);
-static void DetermineSafeOldestOffset(MultiXactId oldestMXact);
 static bool MultiXactOffsetWouldWrap(MultiXactOffset boundary,
 						 MultiXactOffset start, uint32 distance);
-static bool SetOffsetVacuumLimit(bool finish_setup);
+static bool SetOffsetVacuumLimit(void);
 static bool find_multixact_start(MultiXactId multi, MultiXactOffset *result);
 static void WriteMZeroPageXlogRec(int pageno, uint8 info);
+static void WriteMTruncateXlogRec(Oid oldestMultiDB,
+					  MultiXactId startOff, MultiXactId endOff,
+					  MultiXactOffset startMemb, MultiXactOffset endMemb);
 
 
 /*
@@ -1102,7 +1105,7 @@ GetNewMultiXactId(int nmembers, MultiXactOffset *offset)
 	 *----------
 	 */
 #define OFFSET_WARN_SEGMENTS	20
-	if (MultiXactState->offsetStopLimitKnown &&
+	if (MultiXactState->oldestOffsetKnown &&
 		MultiXactOffsetWouldWrap(MultiXactState->offsetStopLimit, nextOffset,
 								 nmembers))
 	{
@@ -1142,7 +1145,7 @@ GetNewMultiXactId(int nmembers, MultiXactOffset *offset)
 			SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
 	}
 
-	if (MultiXactState->offsetStopLimitKnown &&
+	if (MultiXactState->oldestOffsetKnown &&
 		MultiXactOffsetWouldWrap(MultiXactState->offsetStopLimit,
 								 nextOffset,
 								 nmembers + MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT * OFFSET_WARN_SEGMENTS))
@@ -2020,13 +2023,21 @@ StartupMultiXact(void)
 void
 TrimMultiXact(void)
 {
-	MultiXactId multi = MultiXactState->nextMXact;
-	MultiXactOffset offset = MultiXactState->nextOffset;
-	MultiXactId	oldestMXact;
+	MultiXactId nextMXact;
+	MultiXactOffset offset;
+	MultiXactId oldestMXact;
+	Oid			oldestMXactDB;
 	int			pageno;
 	int			entryno;
 	int			flagsoff;
 
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	nextMXact = MultiXactState->nextMXact;
+	offset = MultiXactState->nextOffset;
+	oldestMXact = MultiXactState->oldestMultiXactId;
+	oldestMXactDB = MultiXactState->oldestMultiXactDB;
+	MultiXactState->finishedStartup = true;
+	LWLockRelease(MultiXactGenLock);
 
 	/* Clean up offsets state */
 	LWLockAcquire(MultiXactOffsetControlLock, LW_EXCLUSIVE);
@@ -2034,20 +2045,20 @@ TrimMultiXact(void)
 	/*
 	 * (Re-)Initialize our idea of the latest page number for offsets.
 	 */
-	pageno = MultiXactIdToOffsetPage(multi);
+	pageno = MultiXactIdToOffsetPage(nextMXact);
 	MultiXactOffsetCtl->shared->latest_page_number = pageno;
 
 	/*
 	 * Zero out the remainder of the current offsets page.  See notes in
 	 * TrimCLOG() for motivation.
 	 */
-	entryno = MultiXactIdToOffsetEntry(multi);
+	entryno = MultiXactIdToOffsetEntry(nextMXact);
 	if (entryno != 0)
 	{
 		int			slotno;
 		MultiXactOffset *offptr;
 
-		slotno = SimpleLruReadPage(MultiXactOffsetCtl, pageno, true, multi);
+		slotno = SimpleLruReadPage(MultiXactOffsetCtl, pageno, true, nextMXact);
 		offptr = (MultiXactOffset *) MultiXactOffsetCtl->shared->page_buffer[slotno];
 		offptr += entryno;
 
@@ -2096,12 +2107,11 @@ TrimMultiXact(void)
 
 	LWLockRelease(MultiXactMemberControlLock);
 
-	if (SetOffsetVacuumLimit(true) && IsUnderPostmaster)
-		SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	oldestMXact = MultiXactState->lastCheckpointedOldest;
-	LWLockRelease(MultiXactGenLock);
-	DetermineSafeOldestOffset(oldestMXact);
+	/*
+	 * Now that we are fully started we can accurately compute how far the
+	 * next members wraparound is away.
+	 */
+	SetMultiXactIdLimit(oldestMXact, oldestMXactDB);
 }
 
 /*
@@ -2270,8 +2280,20 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 	 (errmsg("MultiXactId wrap limit is %u, limited by database with OID %u",
 			 multiWrapLimit, oldest_datoid)));
 
+	/*
+	 * Computing the actual limits is only possible once the data directory is
+	 * in a consistent state. There's no need to compute the limits while
+	 * still replaying WAL - no decisions about new multis are made even
+	 * though multixact creations might be replayed. So we'll only do further
+	 * checks after TrimMultiXact() has been called.
+	 */
+	if (!MultiXactState->finishedStartup)
+		return;
+
+	Assert(!InRecovery);
+
 	/* Set limits for offset vacuum. */
-	needs_offset_vacuum = SetOffsetVacuumLimit(false);
+	needs_offset_vacuum = SetOffsetVacuumLimit();
 
 	/*
 	 * If past the autovacuum force point, immediately signal an autovac
@@ -2281,11 +2303,11 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 	 * another iteration immediately if there are still any old databases.
 	 */
 	if ((MultiXactIdPrecedes(multiVacLimit, curMulti) ||
-		 needs_offset_vacuum) && IsUnderPostmaster && !InRecovery)
+		 needs_offset_vacuum) && IsUnderPostmaster)
 		SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
 
 	/* Give an immediate warning if past the wrap warn point */
-	if (MultiXactIdPrecedes(multiWarnLimit, curMulti) && !InRecovery)
+	if (MultiXactIdPrecedes(multiWarnLimit, curMulti))
 	{
 		char	   *oldest_datname;
 
@@ -2353,27 +2375,39 @@ MultiXactAdvanceNextMXact(MultiXactId minMulti,
 }
 
 /*
- * Update our oldestMultiXactId value, but only if it's more recent than
- * what we had.  However, even if not, always update the oldest multixact
- * offset limit.
+ * Update our oldestMultiXactId value, but only if it's more recent than what
+ * we had.
+ *
+ * This may only be called during WAL replay.
  */
 void
 MultiXactAdvanceOldest(MultiXactId oldestMulti, Oid oldestMultiDB)
 {
+	Assert(InRecovery);
+
 	if (MultiXactIdPrecedes(MultiXactState->oldestMultiXactId, oldestMulti))
+	{
+		/*
+		 * If there has been a truncation on the master, detected by seing a
+		 * moving oldestMulti without a corresponding truncation record, we
+		 * know that the primary is still running an older version of postgres
+		 * that doesn't yet log multixact truncations. So perform truncation
+		 * ourselves.
+		 */
+		if (!MultiXactState->sawTruncationInCkptCycle)
+		{
+			ereport(LOG,
+					(errmsg("performing legacy multixact truncation"),
+					 errdetail("Legacy truncations are sometimes performed when replaying WAL from an older primary."),
+					 errhint("Upgrade the primary, it is susceptible to data corruption.")));
+			TruncateMultiXact(oldestMulti, oldestMultiDB, true);
+		}
+
 		SetMultiXactIdLimit(oldestMulti, oldestMultiDB);
-}
+	}
 
-/*
- * Update the "safe truncation point".  This is the newest value of oldestMulti
- * that is known to be flushed as part of a checkpoint record.
- */
-void
-MultiXactSetSafeTruncate(MultiXactId safeTruncateMulti)
-{
-	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-	MultiXactState->lastCheckpointedOldest = safeTruncateMulti;
-	LWLockRelease(MultiXactGenLock);
+	/* only looked at in the startup process, no lock necessary */
+	MultiXactState->sawTruncationInCkptCycle = false;
 }
 
 /*
@@ -2529,126 +2563,50 @@ GetOldestMultiXactId(void)
 }
 
 /*
- * Based on the given oldest MultiXactId, determine what's the oldest member
- * offset and install the limit info in MultiXactState, where it can be used to
- * prevent overrun of old data in the members SLRU area.
- */
-static void
-DetermineSafeOldestOffset(MultiXactId oldestMXact)
-{
-	MultiXactOffset oldestOffset;
-	MultiXactOffset nextOffset;
-	MultiXactOffset offsetStopLimit;
-	MultiXactOffset prevOffsetStopLimit;
-	MultiXactId		nextMXact;
-	bool			finishedStartup;
-	bool			prevOffsetStopLimitKnown;
-
-	/* Fetch values from shared memory. */
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	finishedStartup = MultiXactState->finishedStartup;
-	nextMXact = MultiXactState->nextMXact;
-	nextOffset = MultiXactState->nextOffset;
-	prevOffsetStopLimit = MultiXactState->offsetStopLimit;
-	prevOffsetStopLimitKnown = MultiXactState->offsetStopLimitKnown;
-	LWLockRelease(MultiXactGenLock);
-
-	/* Don't worry about this until after we've started up. */
-	if (!finishedStartup)
-		return;
-
-	/*
-	 * Determine the offset of the oldest multixact.  Normally, we can read
-	 * the offset from the multixact itself, but there's an important special
-	 * case: if there are no multixacts in existence at all, oldestMXact
-	 * obviously can't point to one.  It will instead point to the multixact
-	 * ID that will be assigned the next time one is needed.
-	 *
-	 * NB: oldestMXact should be the oldest multixact that still exists in the
-	 * SLRU, unlike in SetOffsetVacuumLimit, where we do this same computation
-	 * based on the oldest value that might be referenced in a table.
-	 */
-	if (nextMXact == oldestMXact)
-		oldestOffset = nextOffset;
-	else
-	{
-		bool		oldestOffsetKnown;
-
-		oldestOffsetKnown = find_multixact_start(oldestMXact, &oldestOffset);
-		if (!oldestOffsetKnown)
-		{
-			ereport(LOG,
-					(errmsg("MultiXact member wraparound protections are disabled because oldest checkpointed MultiXact %u does not exist on disk",
-						oldestMXact)));
-			return;
-		}
-	}
-
-	/* move back to start of the corresponding segment */
-	offsetStopLimit = oldestOffset - (oldestOffset %
-		(MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT));
-	/* always leave one segment before the wraparound point */
-	offsetStopLimit -= (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT);
-
-	/* if nothing has changed, we're done */
-	if (prevOffsetStopLimitKnown && offsetStopLimit == prevOffsetStopLimit)
-		return;
-
-	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-	MultiXactState->offsetStopLimit = offsetStopLimit;
-	MultiXactState->offsetStopLimitKnown = true;
-	LWLockRelease(MultiXactGenLock);
-
-	if (!prevOffsetStopLimitKnown && IsUnderPostmaster)
-		ereport(LOG,
-				(errmsg("MultiXact member wraparound protections are now enabled")));
-	ereport(DEBUG1,
-			(errmsg("MultiXact member stop limit is now %u based on MultiXact %u",
-				offsetStopLimit, oldestMXact)));
-}
-
-/*
  * Determine how aggressively we need to vacuum in order to prevent member
  * wraparound.
  *
- * To determine the oldest multixact ID, we look at oldestMultiXactId, not
- * lastCheckpointedOldest.  That's because vacuuming can't help with anything
- * older than oldestMultiXactId; anything older than that isn't referenced
- * by any table.  Offsets older than oldestMultiXactId but not as old as
- * lastCheckpointedOldest will go away after the next checkpoint.
+ * To do so determine what's the oldest member offset and install the limit
+ * info in MultiXactState, where it can be used to prevent overrun of old data
+ * in the members SLRU area.
  *
  * The return value is true if emergency autovacuum is required and false
  * otherwise.
  */
 static bool
-SetOffsetVacuumLimit(bool finish_setup)
+SetOffsetVacuumLimit(void)
 {
-	MultiXactId	oldestMultiXactId;
+	MultiXactId oldestMultiXactId;
 	MultiXactId nextMXact;
-	bool		finishedStartup;
-	MultiXactOffset oldestOffset = 0;		/* placate compiler */
+	MultiXactOffset oldestOffset = 0;	/* placate compiler */
+	MultiXactOffset prevOldestOffset;
 	MultiXactOffset nextOffset;
 	bool		oldestOffsetKnown = false;
-	MultiXactOffset prevOldestOffset;
 	bool		prevOldestOffsetKnown;
+	MultiXactOffset offsetStopLimit = 0;
+
+	/*
+	 * NB: Have to prevent concurrent truncation, we might otherwise try to
+	 * lookup a oldestMulti that's concurrently getting truncated away.
+	 */
+	LWLockAcquire(MultiXactTruncationLock, LW_SHARED);
 
 	/* Read relevant fields from shared memory. */
 	LWLockAcquire(MultiXactGenLock, LW_SHARED);
 	oldestMultiXactId = MultiXactState->oldestMultiXactId;
 	nextMXact = MultiXactState->nextMXact;
 	nextOffset = MultiXactState->nextOffset;
-	finishedStartup = MultiXactState->finishedStartup;
-	prevOldestOffset = MultiXactState->oldestOffset;
 	prevOldestOffsetKnown = MultiXactState->oldestOffsetKnown;
+	prevOldestOffset = MultiXactState->oldestOffset;
+	Assert(MultiXactState->finishedStartup);
 	LWLockRelease(MultiXactGenLock);
 
-	/* Don't do this until after any recovery is complete. */
-	if (!finishedStartup && !finish_setup)
-		return false;
-
 	/*
-	 * If no multixacts exist, then oldestMultiXactId will be the next
-	 * multixact that will be created, rather than an existing multixact.
+	 * Determine the offset of the oldest multixact.  Normally, we can read
+	 * the offset from the multixact itself, but there's an important special
+	 * case: if there are no multixacts in existence at all, oldestMXact
+	 * obviously can't point to one.  It will instead point to the multixact
+	 * ID that will be assigned the next time one is needed.
 	 */
 	if (oldestMultiXactId == nextMXact)
 	{
@@ -2669,39 +2627,45 @@ SetOffsetVacuumLimit(bool finish_setup)
 		 */
 		oldestOffsetKnown =
 			find_multixact_start(oldestMultiXactId, &oldestOffset);
+
+		if (oldestOffsetKnown)
+			ereport(DEBUG1,
+					(errmsg("oldest MultiXactId member is at offset %u",
+							oldestOffset)));
+		else
+			ereport(LOG,
+					(errmsg("MultiXact member wraparound protections are disabled because oldest checkpointed MultiXact %u does not exist on disk",
+							oldestMultiXactId)));
 	}
 
+	LWLockRelease(MultiXactTruncationLock);
+
 	/*
-	 * Except when initializing the system for the first time, there's no
-	 * need to update anything if we don't know the oldest offset or if it
-	 * hasn't changed.
+	 * If we can, compute limits (and install them MultiXactState) to prevent
+	 * overrun of old data in the members SLRU area. We can only do so if the
+	 * oldest offset is known though.
 	 */
-	if (finish_setup ||
-		(oldestOffsetKnown && !prevOldestOffsetKnown) ||
-		(oldestOffsetKnown && prevOldestOffset != oldestOffset))
+	if (oldestOffsetKnown)
 	{
-		/* Install the new limits. */
-		LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-		MultiXactState->oldestOffset = oldestOffset;
-		MultiXactState->oldestOffsetKnown = oldestOffsetKnown;
-		MultiXactState->finishedStartup = true;
-		LWLockRelease(MultiXactGenLock);
+		/* move back to start of the corresponding segment */
+		offsetStopLimit = oldestOffset - (oldestOffset %
+					  (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT));
 
-		/* Log the info */
-		if (oldestOffsetKnown)
-			ereport(DEBUG1,
-					(errmsg("oldest MultiXactId member is at offset %u",
-						oldestOffset)));
-		else
-			ereport(DEBUG1,
-					(errmsg("oldest MultiXactId member offset unknown")));
+		/* always leave one segment before the wraparound point */
+		offsetStopLimit -= (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT);
+
+		if (!prevOldestOffsetKnown && IsUnderPostmaster)
+			ereport(LOG,
+					(errmsg("MultiXact member wraparound protections are now enabled")));
+		ereport(DEBUG1,
+		(errmsg("MultiXact member stop limit is now %u based on MultiXact %u",
+				offsetStopLimit, oldestMultiXactId)));
 	}
 
 	/*
 	 * If we failed to get the oldest offset this time, but we have a value
-	 * from a previous pass through this function, assess the need for
-	 * autovacuum based on that old value rather than automatically forcing
-	 * it.
+	 * from a previous pass through this function, use the old value rather
+	 * than automatically forcing it.
 	 */
 	if (prevOldestOffsetKnown && !oldestOffsetKnown)
 	{
@@ -2709,6 +2673,13 @@ SetOffsetVacuumLimit(bool finish_setup)
 		oldestOffsetKnown = true;
 	}
 
+	/* Install the computed values */
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	MultiXactState->oldestOffset = oldestOffset;
+	MultiXactState->oldestOffsetKnown = oldestOffsetKnown;
+	MultiXactState->offsetStopLimit = offsetStopLimit;
+	LWLockRelease(MultiXactGenLock);
+
 	/*
 	 * Do we need an emergency autovacuum?  If we're not sure, assume yes.
 	 */
@@ -2723,7 +2694,7 @@ SetOffsetVacuumLimit(bool finish_setup)
  * boundary point, hence the name.  The reason we don't want to use the regular
  * 2^31-modulo arithmetic here is that we want to be able to use the whole of
  * the 2^32-1 space here, allowing for more multixacts that would fit
- * otherwise.  See also SlruScanDirCbRemoveMembers.
+ * otherwise.
  */
 static bool
 MultiXactOffsetWouldWrap(MultiXactOffset boundary, MultiXactOffset start,
@@ -2769,6 +2740,9 @@ MultiXactOffsetWouldWrap(MultiXactOffset boundary, MultiXactOffset start,
  *
  * Returns false if the file containing the multi does not exist on disk.
  * Otherwise, returns true and sets *result to the starting member offset.
+ *
+ * This function does not prevent concurrent truncation, so if that's
+ * required, the caller has to protect against that.
  */
 static bool
 find_multixact_start(MultiXactId multi, MultiXactOffset *result)
@@ -2779,9 +2753,22 @@ find_multixact_start(MultiXactId multi, MultiXactOffset *result)
 	int			slotno;
 	MultiXactOffset *offptr;
 
+	/* XXX: Remove || AmStartupProcess() after WAL page magic bump */
+	Assert(MultiXactState->finishedStartup || AmStartupProcess());
+
 	pageno = MultiXactIdToOffsetPage(multi);
 	entryno = MultiXactIdToOffsetEntry(multi);
 
+	/*
+	 * We need to flush out dirty data, so PhysicalPageExists can work
+	 * correctly, but SimpleLruFlush() is a pretty big hammer for that.
+	 * Alternatively we could add a in-memory version of page exists, but
+	 * find_multixact_start is called infrequently, and it doesn't seem bad to
+	 * flush buffers to disk before truncation.
+	 */
+	SimpleLruFlush(MultiXactOffsetCtl, true);
+	SimpleLruFlush(MultiXactMemberCtl, true);
+
 	if (!SimpleLruDoesPhysicalPageExist(MultiXactOffsetCtl, pageno))
 		return false;
 
@@ -2887,65 +2874,6 @@ MultiXactMemberFreezeThreshold(void)
 	return multixacts - victim_multixacts;
 }
 
-/*
- * SlruScanDirectory callback.
- *		This callback deletes segments that are outside the range determined by
- *		the given page numbers.
- *
- * Both range endpoints are exclusive (that is, segments containing any of
- * those pages are kept.)
- */
-typedef struct MembersLiveRange
-{
-	int			rangeStart;
-	int			rangeEnd;
-} MembersLiveRange;
-
-static bool
-SlruScanDirCbRemoveMembers(SlruCtl ctl, char *filename, int segpage,
-						   void *data)
-{
-	MembersLiveRange *range = (MembersLiveRange *) data;
-	MultiXactOffset nextOffset;
-
-	if ((segpage == range->rangeStart) ||
-		(segpage == range->rangeEnd))
-		return false;			/* easy case out */
-
-	/*
-	 * To ensure that no segment is spuriously removed, we must keep track of
-	 * new segments added since the start of the directory scan; to do this,
-	 * we update our end-of-range point as we run.
-	 *
-	 * As an optimization, we can skip looking at shared memory if we know for
-	 * certain that the current segment must be kept.  This is so because
-	 * nextOffset never decreases, and we never increase rangeStart during any
-	 * one run.
-	 */
-	if (!((range->rangeStart > range->rangeEnd &&
-		   segpage > range->rangeEnd && segpage < range->rangeStart) ||
-		  (range->rangeStart < range->rangeEnd &&
-		   (segpage < range->rangeStart || segpage > range->rangeEnd))))
-		return false;
-
-	/*
-	 * Update our idea of the end of the live range.
-	 */
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	nextOffset = MultiXactState->nextOffset;
-	LWLockRelease(MultiXactGenLock);
-	range->rangeEnd = MXOffsetToMemberPage(nextOffset);
-
-	/* Recheck the deletion condition.  If it still holds, perform deletion */
-	if ((range->rangeStart > range->rangeEnd &&
-		 segpage > range->rangeEnd && segpage < range->rangeStart) ||
-		(range->rangeStart < range->rangeEnd &&
-		 (segpage < range->rangeStart || segpage > range->rangeEnd)))
-		SlruDeleteSegment(ctl, filename);
-
-	return false;				/* keep going */
-}
-
 typedef struct mxtruncinfo
 {
 	int			earliestExistingPage;
@@ -2969,6 +2897,52 @@ SlruScanDirCbFindEarliest(SlruCtl ctl, char *filename, int segpage, void *data)
 	return false;				/* keep going */
 }
 
+
+/*
+ * Delete member segments [oldest, newOldest)
+ */
+static void
+PerformMembersTruncation(MultiXactOffset oldestOffset, MultiXactOffset newOldestOffset)
+{
+	const int	maxsegment = MXOffsetToMemberSegment(MaxMultiXactOffset);
+	int			startsegment = MXOffsetToMemberSegment(oldestOffset);
+	int			endsegment = MXOffsetToMemberSegment(newOldestOffset);
+	int			segment = startsegment;
+
+	/*
+	 * Delete all the segments but the last one. The last segment can still
+	 * contain, possibly partially, valid data.
+	 */
+	while (segment != endsegment)
+	{
+		elog(DEBUG2, "truncating multixact members segment %x", segment);
+		SlruDeleteSegment(MultiXactMemberCtl, segment);
+
+		/* move to next segment, handling wraparound correctly */
+		if (segment == maxsegment)
+			segment = 0;
+		else
+			segment += 1;
+	}
+}
+
+/*
+ * Delete offsets segments [oldest, newOldest)
+ */
+static void
+PerformOffsetsTruncation(MultiXactId oldestMulti, MultiXactId newOldestMulti)
+{
+	/*
+	 * We step back one multixact to avoid passing a cutoff page that hasn't
+	 * been created yet in the rare case that oldestMulti would be the first
+	 * item on a page and oldestMulti == nextMulti.  In that case, if we
+	 * didn't subtract one, we'd trigger SimpleLruTruncate's wraparound
+	 * detection.
+	 */
+	SimpleLruTruncate(MultiXactOffsetCtl,
+				  MultiXactIdToOffsetPage(PreviousMultiXactId(newOldestMulti)));
+}
+
 /*
  * Remove all MultiXactOffset and MultiXactMember segments before the oldest
  * ones still of interest.
@@ -2979,27 +2953,54 @@ SlruScanDirCbFindEarliest(SlruCtl ctl, char *filename, int segpage, void *data)
  * xlog_redo() will already have called MultiXactAdvanceOldest().  Our
  * latest_page_number will already have been initialized by StartupMultiXact()
  * and kept up to date as new pages are zeroed.
+ *
+ * newOldestMulti is the oldest currently required multixact, newOldestMultiDB
+ * is one of the databases preventing newOldestMulti from increasing.
  */
 void
-TruncateMultiXact(void)
+TruncateMultiXact(MultiXactId newOldestMulti, Oid newOldestMultiDB, bool in_recovery)
 {
-	MultiXactId oldestMXact;
+	MultiXactId oldestMulti;
+	MultiXactId nextMulti;
+	MultiXactOffset newOldestOffset;
 	MultiXactOffset oldestOffset;
-	MultiXactId		nextMXact;
-	MultiXactOffset	nextOffset;
+	MultiXactOffset nextOffset;
 	mxtruncinfo trunc;
 	MultiXactId earliest;
-	MembersLiveRange range;
 
-	Assert(AmCheckpointerProcess() || AmStartupProcess() ||
-		   !IsPostmasterEnvironment);
+	/*
+	 * Need to allow being called in recovery for backwards compatibility,
+	 * when an updated standby replays WAL generated by a non-updated primary.
+	 */
+	Assert(in_recovery || !RecoveryInProgress());
+	Assert(!in_recovery || AmStartupProcess());
+	Assert(in_recovery || MultiXactState->finishedStartup);
+
+	/*
+	 * We can only allow one truncation to happen at once. Otherwise parts of
+	 * members might vanish while we're doing lookups or similar. There's no
+	 * need to have an interlock with creating new multis or such, since those
+	 * are constrained by the limits (which only grow, never shrink).
+	 */
+	LWLockAcquire(MultiXactTruncationLock, LW_EXCLUSIVE);
 
 	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	oldestMXact = MultiXactState->lastCheckpointedOldest;
-	nextMXact = MultiXactState->nextMXact;
+	nextMulti = MultiXactState->nextMXact;
 	nextOffset = MultiXactState->nextOffset;
+	oldestMulti = MultiXactState->oldestMultiXactId;
 	LWLockRelease(MultiXactGenLock);
-	Assert(MultiXactIdIsValid(oldestMXact));
+	Assert(MultiXactIdIsValid(oldestMulti));
+
+	/*
+	 * Make sure to only attempt truncation if there's values to truncate
+	 * away. In normal processing values shouldn't go backwards, but there's
+	 * some corner cases (due to bugs) where that's possible.
+	 */
+	if (MultiXactIdPrecedesOrEquals(newOldestMulti, oldestMulti))
+	{
+		LWLockRelease(MultiXactTruncationLock);
+		return;
+	}
 
 	/*
 	 * Note we can't just plow ahead with the truncation; it's possible that
@@ -3007,6 +3008,9 @@ TruncateMultiXact(void)
 	 * going to attempt to read the offsets page to determine where to
 	 * truncate the members SLRU.  So we first scan the directory to determine
 	 * the earliest offsets page number that we can read without error.
+	 *
+	 * NB: It's also possible that the page that oldestMulti is on has already
+	 * been truncated away, and we crashed before updating oldestMulti.
 	 */
 	trunc.earliestExistingPage = -1;
 	SlruScanDirectory(MultiXactOffsetCtl, SlruScanDirCbFindEarliest, &trunc);
@@ -3014,19 +3018,10 @@ TruncateMultiXact(void)
 	if (earliest < FirstMultiXactId)
 		earliest = FirstMultiXactId;
 
-	/*
-	 * If there's nothing to remove, we can bail out early.
-	 *
-	 * Due to bugs in early releases of PostgreSQL 9.3.X and 9.4.X,
-	 * oldestMXact might point to a multixact that does not exist.
-	 * Autovacuum will eventually advance it to a value that does exist,
-	 * and we want to set a proper offsetStopLimit when that happens,
-	 * so call DetermineSafeOldestOffset here even if we're not actually
-	 * truncating.
-	 */
-	if (MultiXactIdPrecedes(oldestMXact, earliest))
+	/* If there's nothing to remove, we can bail out early. */
+	if (MultiXactIdPrecedes(oldestMulti, earliest))
 	{
-		DetermineSafeOldestOffset(oldestMXact);
+		LWLockRelease(MultiXactTruncationLock);
 		return;
 	}
 
@@ -3038,46 +3033,95 @@ TruncateMultiXact(void)
 	 * already checked that it doesn't precede the earliest MultiXact on
 	 * disk.  But if it fails, don't truncate anything, and log a message.
 	 */
-	if (oldestMXact == nextMXact)
+	if (oldestMulti == nextMulti)
 		oldestOffset = nextOffset;		/* there are NO MultiXacts */
-	else if (!find_multixact_start(oldestMXact, &oldestOffset))
+	else if (!find_multixact_start(oldestMulti, &oldestOffset))
 	{
 		ereport(LOG,
 				(errmsg("oldest MultiXact %u not found, earliest MultiXact %u, skipping truncation",
-					oldestMXact, earliest)));
+						oldestMulti, earliest)));
+		LWLockRelease(MultiXactTruncationLock);
 		return;
 	}
 
 	/*
-	 * To truncate MultiXactMembers, we need to figure out the active page
-	 * range and delete all files outside that range.  The start point is the
-	 * start of the segment containing the oldest offset; an end point of the
-	 * segment containing the next offset to use is enough.  The end point is
-	 * updated as MultiXactMember gets extended concurrently, elsewhere.
+	 * Secondly compute up to where to truncate. Lookup the corresponding
+	 * member offset for newOldestMulti for that.
 	 */
-	range.rangeStart = MXOffsetToMemberPage(oldestOffset);
-	range.rangeStart -= range.rangeStart % SLRU_PAGES_PER_SEGMENT;
-
-	range.rangeEnd = MXOffsetToMemberPage(nextOffset);
+	if (newOldestMulti == nextMulti)
+		newOldestOffset = nextOffset; /* there are NO MultiXacts */
+	else if (!find_multixact_start(newOldestMulti, &newOldestOffset))
+	{
+		ereport(LOG,
+				(errmsg("cannot truncate up toMultiXact %u because it does not exist on disk, skipping truncation",
+						newOldestMulti)));
+		LWLockRelease(MultiXactTruncationLock);
+		return;
+	}
 
-	SlruScanDirectory(MultiXactMemberCtl, SlruScanDirCbRemoveMembers, &range);
+	elog(DEBUG1, "performing multixact truncation: "
+		 "offsets [%u, %u), offset segments [%x, %x), "
+		 "members [%u, %u), member segments [%x, %x)",
+		 oldestMulti, newOldestMulti,
+		 MultiXactIdToOffsetSegment(oldestMulti),
+		 MultiXactIdToOffsetSegment(newOldestMulti),
+		 oldestOffset, newOldestOffset,
+		 MXOffsetToMemberSegment(oldestOffset),
+		 MXOffsetToMemberSegment(newOldestOffset));
 
 	/*
-	 * Now we can truncate MultiXactOffset.  We step back one multixact to
-	 * avoid passing a cutoff page that hasn't been created yet in the rare
-	 * case that oldestMXact would be the first item on a page and oldestMXact
-	 * == nextMXact.  In that case, if we didn't subtract one, we'd trigger
-	 * SimpleLruTruncate's wraparound detection.
+	 * Do truncation, and the WAL logging of the truncation, in a critical
+	 * section. That way offsets/members cannot get out of sync anymore, i.e.
+	 * once consistent the newOldestMulti will always exist in members, even if
+	 * we crashed in the wrong moment.
 	 */
-	SimpleLruTruncate(MultiXactOffsetCtl,
-				  MultiXactIdToOffsetPage(PreviousMultiXactId(oldestMXact)));
+	START_CRIT_SECTION();
 
 	/*
-	 * Now, and only now, we can advance the stop point for multixact members.
-	 * If we did it any sooner, the segments we deleted above might already
-	 * have been overwritten with new members.  That would be bad.
+	 * Prevent checkpoints from being scheduled concurrently. This is critical
+	 * because otherwise a truncation record might not be replayed after a
+	 * crash/basebackup, even though the state of the data directory would
+	 * require it.  It's not possible (startup process doesn't have a PGXACT
+	 * entry), and not needed, to do this during recovery, when performing an
+	 * old-style truncation, though. There the entire scheduling depends on
+	 * the replayed WAL records which be the same after a possible crash.
+	 */
+	if (!in_recovery)
+	{
+		Assert(!MyPgXact->delayChkpt);
+		MyPgXact->delayChkpt = true;
+	}
+
+	/* WAL log truncation */
+	if (!in_recovery)
+		WriteMTruncateXlogRec(newOldestMultiDB,
+							  oldestMulti, newOldestMulti,
+							  oldestOffset, newOldestOffset);
+
+	/*
+	 * Update in-memory limits before performing the truncation, while inside
+	 * the critical section: Have to do it before truncation, to prevent
+	 * concurrent lookups of those values. Has to be inside the critical
+	 * section as otherwise a future call to this function would error out,
+	 * while looking up the oldest member in offsets, if our caller crashes
+	 * before updating the limits.
 	 */
-	DetermineSafeOldestOffset(oldestMXact);
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	MultiXactState->oldestMultiXactId = newOldestMulti;
+	MultiXactState->oldestMultiXactDB = newOldestMultiDB;
+	LWLockRelease(MultiXactGenLock);
+
+	/* First truncate members */
+	PerformMembersTruncation(oldestOffset, newOldestOffset);
+
+	/* Then offsets */
+	PerformOffsetsTruncation(oldestMulti, newOldestMulti);
+
+	if (!in_recovery)
+		MyPgXact->delayChkpt = false;
+
+	END_CRIT_SECTION();
+	LWLockRelease(MultiXactTruncationLock);
 }
 
 /*
@@ -3174,6 +3218,34 @@ WriteMZeroPageXlogRec(int pageno, uint8 info)
 }
 
 /*
+ * Write a TRUNCATE xlog record
+ *
+ * We must flush the xlog record to disk before returning --- see notes in
+ * TruncateCLOG().
+ */
+static void
+WriteMTruncateXlogRec(Oid oldestMultiDB,
+					  MultiXactId startTruncOff, MultiXactId endTruncOff,
+				MultiXactOffset startTruncMemb, MultiXactOffset endTruncMemb)
+{
+	XLogRecPtr	recptr;
+	xl_multixact_truncate xlrec;
+
+	xlrec.oldestMultiDB = oldestMultiDB;
+
+	xlrec.startTruncOff = startTruncOff;
+	xlrec.endTruncOff = endTruncOff;
+
+	xlrec.startTruncMemb = startTruncMemb;
+	xlrec.endTruncMemb = endTruncMemb;
+
+	XLogBeginInsert();
+	XLogRegisterData((char *) (&xlrec), SizeOfMultiXactTruncate);
+	recptr = XLogInsert(RM_MULTIXACT_ID, XLOG_MULTIXACT_TRUNCATE_ID);
+	XLogFlush(recptr);
+}
+
+/*
  * MULTIXACT resource manager's routines
  */
 void
@@ -3255,6 +3327,49 @@ multixact_redo(XLogReaderState *record)
 			LWLockRelease(XidGenLock);
 		}
 	}
+	else if (info == XLOG_MULTIXACT_TRUNCATE_ID)
+	{
+		xl_multixact_truncate xlrec;
+		int			pageno;
+
+		memcpy(&xlrec, XLogRecGetData(record),
+			   SizeOfMultiXactTruncate);
+
+		elog(DEBUG1, "replaying multixact truncation: "
+			 "offsets [%u, %u), offset segments [%x, %x), "
+			 "members [%u, %u), member segments [%x, %x)",
+			 xlrec.startTruncOff, xlrec.endTruncOff,
+			 MultiXactIdToOffsetSegment(xlrec.startTruncOff),
+			 MultiXactIdToOffsetSegment(xlrec.endTruncOff),
+			 xlrec.startTruncMemb, xlrec.endTruncMemb,
+			 MXOffsetToMemberSegment(xlrec.startTruncMemb),
+			 MXOffsetToMemberSegment(xlrec.endTruncMemb));
+
+		/* should not be required, but more than cheap enough */
+		LWLockAcquire(MultiXactTruncationLock, LW_EXCLUSIVE);
+
+		/*
+		 * Advance the horizon values, so they're current at the end of
+		 * recovery.
+		 */
+		SetMultiXactIdLimit(xlrec.endTruncOff, xlrec.oldestMultiDB);
+
+		PerformMembersTruncation(xlrec.startTruncMemb, xlrec.endTruncMemb);
+
+		/*
+		 * During XLOG replay, latest_page_number isn't necessarily set up
+		 * yet; insert a suitable value to bypass the sanity test in
+		 * SimpleLruTruncate.
+		 */
+		pageno = MultiXactIdToOffsetPage(xlrec.endTruncOff);
+		MultiXactOffsetCtl->shared->latest_page_number = pageno;
+		PerformOffsetsTruncation(xlrec.startTruncOff, xlrec.endTruncOff);
+
+		LWLockRelease(MultiXactTruncationLock);
+
+		/* only looked at in the startup process, no lock necessary */
+		MultiXactState->sawTruncationInCkptCycle = true;
+	}
 	else
 		elog(PANIC, "multixact_redo: unknown op code %u", info);
 }
diff --git a/src/backend/access/transam/slru.c b/src/backend/access/transam/slru.c
index 5fcea11..90c7cf5 100644
--- a/src/backend/access/transam/slru.c
+++ b/src/backend/access/transam/slru.c
@@ -134,6 +134,7 @@ static int	SlruSelectLRUPage(SlruCtl ctl, int pageno);
 
 static bool SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename,
 						  int segpage, void *data);
+static void SlruInternalDeleteSegment(SlruCtl ctl, char *filename);
 
 /*
  * Initialization of shared memory
@@ -1075,7 +1076,7 @@ SlruSelectLRUPage(SlruCtl ctl, int pageno)
  * Flush dirty pages to disk during checkpoint or database shutdown
  */
 void
-SimpleLruFlush(SlruCtl ctl, bool checkpoint)
+SimpleLruFlush(SlruCtl ctl, bool allow_redirtied)
 {
 	SlruShared	shared = ctl->shared;
 	SlruFlushData fdata;
@@ -1096,11 +1097,11 @@ SimpleLruFlush(SlruCtl ctl, bool checkpoint)
 		SlruInternalWritePage(ctl, slotno, &fdata);
 
 		/*
-		 * When called during a checkpoint, we cannot assert that the slot is
-		 * clean now, since another process might have re-dirtied it already.
-		 * That's okay.
+		 * In some places (e.g. checkpoints), we cannot assert that the slot
+		 * is clean now, since another process might have re-dirtied it
+		 * already.  That's okay.
 		 */
-		Assert(checkpoint ||
+		Assert(allow_redirtied ||
 			   shared->page_status[slotno] == SLRU_PAGE_EMPTY ||
 			   (shared->page_status[slotno] == SLRU_PAGE_VALID &&
 				!shared->page_dirty[slotno]));
@@ -1210,8 +1211,14 @@ restart:;
 	(void) SlruScanDirectory(ctl, SlruScanDirCbDeleteCutoff, &cutoffPage);
 }
 
-void
-SlruDeleteSegment(SlruCtl ctl, char *filename)
+/*
+ * Delete an individual SLRU segment, identified by the filename.
+ *
+ * NB: This does not touch the SLRU buffers themselves, callers have to ensure
+ * they either can't yet contain anything, or have already been cleaned out.
+ */
+static void
+SlruInternalDeleteSegment(SlruCtl ctl, char *filename)
 {
 	char		path[MAXPGPATH];
 
@@ -1222,6 +1229,64 @@ SlruDeleteSegment(SlruCtl ctl, char *filename)
 }
 
 /*
+ * Delete an individual SLRU segment, identified by the segment number.
+ */
+void
+SlruDeleteSegment(SlruCtl ctl, int segno)
+{
+	SlruShared	shared = ctl->shared;
+	int			slotno;
+	char		path[MAXPGPATH];
+	bool		did_write;
+
+	/* Clean out any possibly existing references to the segment. */
+	LWLockAcquire(shared->ControlLock, LW_EXCLUSIVE);
+restart:
+	did_write = false;
+	for (slotno = 0; slotno < shared->num_slots; slotno++)
+	{
+		int			pagesegno = shared->page_number[slotno] / SLRU_PAGES_PER_SEGMENT;
+
+		if (shared->page_status[slotno] == SLRU_PAGE_EMPTY)
+			continue;
+
+		/* not the segment we're looking for */
+		if (pagesegno != segno)
+			continue;
+
+		/* If page is clean, just change state to EMPTY (expected case). */
+		if (shared->page_status[slotno] == SLRU_PAGE_VALID &&
+			!shared->page_dirty[slotno])
+		{
+			shared->page_status[slotno] = SLRU_PAGE_EMPTY;
+			continue;
+		}
+
+		/* Same logic as SimpleLruTruncate() */
+		if (shared->page_status[slotno] == SLRU_PAGE_VALID)
+			SlruInternalWritePage(ctl, slotno, NULL);
+		else
+			SimpleLruWaitIO(ctl, slotno);
+
+		did_write = true;
+	}
+
+	/*
+	 * Be extra careful and re-check. The IO functions release the control
+	 * lock, so new pages could have been read in.
+	 */
+	if (did_write)
+		goto restart;
+
+	snprintf(path, MAXPGPATH, "%s/%04X", ctl->Dir, segno);
+	ereport(DEBUG2,
+			(errmsg("removing file \"%s\"", path)));
+	unlink(path);
+
+	LWLockRelease(shared->ControlLock);
+}
+
+/*
  * SlruScanDirectory callback
  *		This callback reports true if there's any segment prior to the one
  *		containing the page passed as "data".
@@ -1249,7 +1314,7 @@ SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename, int segpage, void *data)
 	int			cutoffPage = *(int *) data;
 
 	if (ctl->PagePrecedes(segpage, cutoffPage))
-		SlruDeleteSegment(ctl, filename);
+		SlruInternalDeleteSegment(ctl, filename);
 
 	return false;				/* keep going */
 }
@@ -1261,7 +1326,7 @@ SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename, int segpage, void *data)
 bool
 SlruScanDirCbDeleteAll(SlruCtl ctl, char *filename, int segpage, void *data)
 {
-	SlruDeleteSegment(ctl, filename);
+	SlruInternalDeleteSegment(ctl, filename);
 
 	return false;				/* keep going */
 }
diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index a87f09e..1ac1c05 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -6330,7 +6330,6 @@ StartupXLOG(void)
 	SetMultiXactIdLimit(checkPoint.oldestMulti, checkPoint.oldestMultiDB);
 	SetCommitTsLimit(checkPoint.oldestCommitTs,
 					 checkPoint.newestCommitTs);
-	MultiXactSetSafeTruncate(checkPoint.oldestMulti);
 	XLogCtl->ckptXidEpoch = checkPoint.nextXidEpoch;
 	XLogCtl->ckptXid = checkPoint.nextXid;
 
@@ -6347,10 +6346,8 @@ StartupXLOG(void)
 	StartupReorderBuffer();
 
 	/*
-	 * Startup MultiXact.  We need to do this early for two reasons: one is
-	 * that we might try to access multixacts when we do tuple freezing, and
-	 * the other is we need its state initialized because we attempt
-	 * truncation during restartpoints.
+	 * Startup MultiXact. We need to do this early to be able to replay
+	 * truncations.
 	 */
 	StartupMultiXact();
 
@@ -8508,12 +8505,6 @@ CreateCheckPoint(int flags)
 	END_CRIT_SECTION();
 
 	/*
-	 * Now that the checkpoint is safely on disk, we can update the point to
-	 * which multixact can be truncated.
-	 */
-	MultiXactSetSafeTruncate(checkPoint.oldestMulti);
-
-	/*
 	 * Let smgr do post-checkpoint cleanup (eg, deleting old files).
 	 */
 	smgrpostckpt();
@@ -8552,11 +8543,6 @@ CreateCheckPoint(int flags)
 	if (!RecoveryInProgress())
 		TruncateSUBTRANS(GetOldestXmin(NULL, false));
 
-	/*
-	 * Truncate pg_multixact too.
-	 */
-	TruncateMultiXact();
-
 	/* Real work is done, but log and update stats before releasing lock. */
 	LogCheckpointEnd(false);
 
@@ -8887,21 +8873,6 @@ CreateRestartPoint(int flags)
 	}
 
 	/*
-	 * Due to a historical accident multixact truncations are not WAL-logged,
-	 * but just performed everytime the mxact horizon is increased. So, unless
-	 * we explicitly execute truncations on a standby it will never clean out
-	 * /pg_multixact which obviously is bad, both because it uses space and
-	 * because we can wrap around into pre-existing data...
-	 *
-	 * We can only do the truncation here, after the UpdateControlFile()
-	 * above, because we've now safely established a restart point.  That
-	 * guarantees we will not need to access those multis.
-	 *
-	 * It's probably worth improving this.
-	 */
-	TruncateMultiXact();
-
-	/*
 	 * Truncate pg_subtrans if possible.  We can throw away all data before
 	 * the oldest XMIN of any running transaction.  No future transaction will
 	 * attempt to reference any pg_subtrans entry older than that (see Asserts
@@ -9261,9 +9232,14 @@ xlog_redo(XLogReaderState *record)
 		LWLockRelease(OidGenLock);
 		MultiXactSetNextMXact(checkPoint.nextMulti,
 							  checkPoint.nextMultiOffset);
+
+		/*
+		 * NB: This may perform multixact truncation when replaying WAL
+		 * generated by an older primary.
+		 */
+		MultiXactAdvanceOldest(checkPoint.oldestMulti,
+							   checkPoint.oldestMultiDB);
 		SetTransactionIdLimit(checkPoint.oldestXid, checkPoint.oldestXidDB);
-		SetMultiXactIdLimit(checkPoint.oldestMulti, checkPoint.oldestMultiDB);
-		MultiXactSetSafeTruncate(checkPoint.oldestMulti);
 
 		/*
 		 * If we see a shutdown checkpoint while waiting for an end-of-backup
@@ -9353,14 +9329,17 @@ xlog_redo(XLogReaderState *record)
 		LWLockRelease(OidGenLock);
 		MultiXactAdvanceNextMXact(checkPoint.nextMulti,
 								  checkPoint.nextMultiOffset);
+
+		/*
+		 * NB: This may perform multixact truncation when replaying WAL
+		 * generated by an older primary.
+		 */
+		MultiXactAdvanceOldest(checkPoint.oldestMulti,
+							   checkPoint.oldestMultiDB);
 		if (TransactionIdPrecedes(ShmemVariableCache->oldestXid,
 								  checkPoint.oldestXid))
 			SetTransactionIdLimit(checkPoint.oldestXid,
 								  checkPoint.oldestXidDB);
-		MultiXactAdvanceOldest(checkPoint.oldestMulti,
-							   checkPoint.oldestMultiDB);
-		MultiXactSetSafeTruncate(checkPoint.oldestMulti);
-
 		/* ControlFile->checkPointCopy always tracks the latest ckpt XID */
 		ControlFile->checkPointCopy.nextXidEpoch = checkPoint.nextXidEpoch;
 		ControlFile->checkPointCopy.nextXid = checkPoint.nextXid;
diff --git a/src/backend/commands/vacuum.c b/src/backend/commands/vacuum.c
index 85b0483..698bb35 100644
--- a/src/backend/commands/vacuum.c
+++ b/src/backend/commands/vacuum.c
@@ -1137,11 +1137,11 @@ vac_truncate_clog(TransactionId frozenXID,
 		return;
 
 	/*
-	 * Truncate CLOG and CommitTs to the oldest computed value. Note we don't
-	 * truncate multixacts; that will be done by the next checkpoint.
+	 * Truncate CLOG, multixact and CommitTs to the oldest computed value.
 	 */
 	TruncateCLOG(frozenXID);
 	TruncateCommitTs(frozenXID, true);
+	TruncateMultiXact(minMulti, minmulti_datoid, false);
 
 	/*
 	 * Update the wrap limit for GetNewTransactionId and creation of new
diff --git a/src/backend/storage/lmgr/lwlocknames.txt b/src/backend/storage/lmgr/lwlocknames.txt
index 96bbfe8..c557cb6 100644
--- a/src/backend/storage/lmgr/lwlocknames.txt
+++ b/src/backend/storage/lmgr/lwlocknames.txt
@@ -45,3 +45,4 @@ ReplicationSlotControlLock			37
 CommitTsControlLock					38
 CommitTsLock						39
 ReplicationOriginLock				40
+MultiXactTruncationLock				41
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index 6213f8a..47ef38d 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -71,6 +71,7 @@ typedef struct MultiXactMember
 #define XLOG_MULTIXACT_ZERO_OFF_PAGE	0x00
 #define XLOG_MULTIXACT_ZERO_MEM_PAGE	0x10
 #define XLOG_MULTIXACT_CREATE_ID		0x20
+#define XLOG_MULTIXACT_TRUNCATE_ID		0x30
 
 typedef struct xl_multixact_create
 {
@@ -82,6 +83,21 @@ typedef struct xl_multixact_create
 
 #define SizeOfMultiXactCreate (offsetof(xl_multixact_create, members))
 
+typedef struct xl_multixact_truncate
+{
+	Oid			oldestMultiDB;
+
+	/* to-be-truncated range of multixact offsets */
+	MultiXactId startTruncOff;	/* just for completeness' sake */
+	MultiXactId endTruncOff;
+
+	/* to-be-truncated range of multixact members */
+	MultiXactOffset startTruncMemb;
+	MultiXactOffset endTruncMemb;
+} xl_multixact_truncate;
+
+#define SizeOfMultiXactTruncate (sizeof(xl_multixact_truncate))
+
 
 extern MultiXactId MultiXactIdCreate(TransactionId xid1,
 				  MultiXactStatus status1, TransactionId xid2,
@@ -120,13 +136,12 @@ extern void MultiXactGetCheckptMulti(bool is_shutdown,
 						 Oid *oldestMultiDB);
 extern void CheckPointMultiXact(void);
 extern MultiXactId GetOldestMultiXactId(void);
-extern void TruncateMultiXact(void);
+extern void TruncateMultiXact(MultiXactId oldestMulti, Oid oldestMultiDB, bool in_recovery);
 extern void MultiXactSetNextMXact(MultiXactId nextMulti,
 					  MultiXactOffset nextMultiOffset);
 extern void MultiXactAdvanceNextMXact(MultiXactId minMulti,
 						  MultiXactOffset minMultiOffset);
 extern void MultiXactAdvanceOldest(MultiXactId oldestMulti, Oid oldestMultiDB);
-extern void MultiXactSetSafeTruncate(MultiXactId safeTruncateMulti);
 extern int	MultiXactMemberFreezeThreshold(void);
 
 extern void multixact_twophase_recover(TransactionId xid, uint16 info,
diff --git a/src/include/access/slru.h b/src/include/access/slru.h
index 9c7f019..f60e75b 100644
--- a/src/include/access/slru.h
+++ b/src/include/access/slru.h
@@ -143,14 +143,14 @@ extern int SimpleLruReadPage(SlruCtl ctl, int pageno, bool write_ok,
 extern int SimpleLruReadPage_ReadOnly(SlruCtl ctl, int pageno,
 						   TransactionId xid);
 extern void SimpleLruWritePage(SlruCtl ctl, int slotno);
-extern void SimpleLruFlush(SlruCtl ctl, bool checkpoint);
+extern void SimpleLruFlush(SlruCtl ctl, bool allow_redirtied);
 extern void SimpleLruTruncate(SlruCtl ctl, int cutoffPage);
 extern bool SimpleLruDoesPhysicalPageExist(SlruCtl ctl, int pageno);
 
 typedef bool (*SlruScanCallback) (SlruCtl ctl, char *filename, int segpage,
 											  void *data);
 extern bool SlruScanDirectory(SlruCtl ctl, SlruScanCallback callback, void *data);
-extern void SlruDeleteSegment(SlruCtl ctl, char *filename);
+extern void SlruDeleteSegment(SlruCtl ctl, int segno);
 
 /* SlruScanDirectory public callbacks */
 extern bool SlruScanDirCbReportPresence(SlruCtl ctl, char *filename,
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index a037f81..0e149ea 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2750,6 +2750,7 @@ xl_invalid_page
 xl_invalid_page_key
 xl_multi_insert_tuple
 xl_multixact_create
+xl_multixact_truncate
 xl_parameter_change
 xl_relmap_update
 xl_replorigin_drop
-- 
2.5.0.400.gff86faf

>From b407a8ca516f7693d6a5166b06e7d9137c7c5d50 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Thu, 24 Sep 2015 15:50:01 +0200
Subject: [PATCH 3/3] Remove legacy multixact truncation support.

---
 src/backend/access/transam/multixact.c | 77 +++++++---------------------------
 src/backend/commands/vacuum.c          |  2 +-
 src/include/access/multixact.h         |  2 +-
 src/include/access/xlog_internal.h     |  2 +-
 4 files changed, 17 insertions(+), 66 deletions(-)

diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index d19b4c2..43f6e99 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -220,14 +220,6 @@ typedef struct MultiXactStateData
 	MultiXactOffset oldestOffset;
 	bool		oldestOffsetKnown;
 
-	/*
-	 * True if a multixact truncation WAL record was replayed since the last
-	 * checkpoint. This is used to trigger 'legacy truncations', i.e. truncate
-	 * by looking at the data directory during WAL replay, when the primary is
-	 * too old to generate truncation records.
-	 */
-	bool		sawTruncationInCkptCycle;
-
 	/* support for anti-wraparound measures */
 	MultiXactId multiVacLimit;
 	MultiXactId multiWarnLimit;
@@ -2384,28 +2376,7 @@ MultiXactAdvanceOldest(MultiXactId oldestMulti, Oid oldestMultiDB)
 	Assert(InRecovery);
 
 	if (MultiXactIdPrecedes(MultiXactState->oldestMultiXactId, oldestMulti))
-	{
-		/*
-		 * If there has been a truncation on the master, detected by seeing a
-		 * moving oldestMulti, without a corresponding truncation record, we
-		 * know that the primary is still running an older version of postgres
-		 * that doesn't yet log multixact truncations. So perform the
-		 * truncation ourselves.
-		 */
-		if (!MultiXactState->sawTruncationInCkptCycle)
-		{
-			ereport(LOG,
-					(errmsg("performing legacy multixact truncation"),
-					 errdetail("Legacy truncations are sometimes performed when replaying WAL from an older primary."),
-					 errhint("Upgrade the primary, it is susceptible to data corruption.")));
-			TruncateMultiXact(oldestMulti, oldestMultiDB, true);
-		}
-
 		SetMultiXactIdLimit(oldestMulti, oldestMultiDB);
-	}
-
-	/* only looked at in the startup process, no lock necessary */
-	MultiXactState->sawTruncationInCkptCycle = false;
 }
 
 /*
@@ -2750,8 +2721,7 @@ find_multixact_start(MultiXactId multi, MultiXactOffset *result)
 	int			slotno;
 	MultiXactOffset *offptr;
 
-	/* XXX: Remove || AmStartupProcess() after WAL page magic bump */
-	Assert(MultiXactState->finishedStartup || AmStartupProcess());
+	Assert(MultiXactState->finishedStartup);
 
 	pageno = MultiXactIdToOffsetPage(multi);
 	entryno = MultiXactIdToOffsetEntry(multi);
@@ -2944,18 +2914,15 @@ PerformOffsetsTruncation(MultiXactId oldestMulti, MultiXactId newOldestMulti)
  * Remove all MultiXactOffset and MultiXactMember segments before the oldest
  * ones still of interest.
  *
- * On a primary this is called as part of vacuum (via
- * vac_truncate_clog()). During recovery truncation is normally done by
- * replaying truncation WAL records instead of this routine; the exception is
- * when replaying records from an older primary that doesn't yet generate
- * truncation WAL records. In that case truncation is triggered by
- * MultiXactAdvanceOldest().
+ * This is only called on a primary as part of vacuum (via
+ * vac_truncate_clog()). During recovery truncation is done by replaying
+ * truncation WAL records logged here.
  *
  * newOldestMulti is the oldest currently required multixact, newOldestMultiDB
  * is one of the databases preventing newOldestMulti from increasing.
  */
 void
-TruncateMultiXact(MultiXactId newOldestMulti, Oid newOldestMultiDB, bool in_recovery)
+TruncateMultiXact(MultiXactId newOldestMulti, Oid newOldestMultiDB)
 {
 	MultiXactId oldestMulti;
 	MultiXactId nextMulti;
@@ -2965,13 +2932,8 @@ TruncateMultiXact(MultiXactId newOldestMulti, Oid newOldestMultiDB, bool in_reco
 	mxtruncinfo trunc;
 	MultiXactId earliest;
 
-	/*
-	 * Need to allow being called in recovery for backwards compatibility,
-	 * when an updated standby replays WAL generated by a non-updated primary.
-	 */
-	Assert(in_recovery || !RecoveryInProgress());
-	Assert(!in_recovery || AmStartupProcess());
-	Assert(in_recovery || MultiXactState->finishedStartup);
+	Assert(!RecoveryInProgress());
+	Assert(MultiXactState->finishedStartup);
 
 	/*
 	 * We can only allow one truncation to happen at once. Otherwise parts of
@@ -3084,22 +3046,15 @@ TruncateMultiXact(MultiXactId newOldestMulti, Oid newOldestMultiDB, bool in_reco
 	 * Prevent checkpoints from being scheduled concurrently. This is critical
 	 * because otherwise a truncation record might not be replayed after a
 	 * crash/basebackup, even though the state of the data directory would
-	 * require it.  It's not possible (startup process doesn't have a PGXACT
-	 * entry), and not needed, to do this during recovery, when performing an
-	 * old-style truncation, though. There the entire scheduling depends on
-	 * the replayed WAL records which be the same after a possible crash.
+	 * require it.
 	 */
-	if (!in_recovery)
-	{
-		Assert(!MyPgXact->delayChkpt);
-		MyPgXact->delayChkpt = true;
-	}
+	Assert(!MyPgXact->delayChkpt);
+	MyPgXact->delayChkpt = true;
 
 	/* WAL log truncation */
-	if (!in_recovery)
-		WriteMTruncateXlogRec(newOldestMultiDB,
-							  oldestMulti, newOldestMulti,
-							  oldestOffset, newOldestOffset);
+	WriteMTruncateXlogRec(newOldestMultiDB,
+						  oldestMulti, newOldestMulti,
+						  oldestOffset, newOldestOffset);
 
 	/*
 	 * Update in-memory limits before performing the truncation, while inside
@@ -3120,8 +3075,7 @@ TruncateMultiXact(MultiXactId newOldestMulti, Oid newOldestMultiDB, bool in_reco
 	/* Then offsets */
 	PerformOffsetsTruncation(oldestMulti, newOldestMulti);
 
-	if (!in_recovery)
-		MyPgXact->delayChkpt = false;
+	MyPgXact->delayChkpt = false;
 
 	END_CRIT_SECTION();
 	LWLockRelease(MultiXactTruncationLock);
@@ -3369,9 +3323,6 @@ multixact_redo(XLogReaderState *record)
 		PerformOffsetsTruncation(xlrec.startTruncOff, xlrec.endTruncOff);
 
 		LWLockRelease(MultiXactTruncationLock);
-
-		/* only looked at in the startup process, no lock necessary */
-		MultiXactState->sawTruncationInCkptCycle = true;
 	}
 	else
 		elog(PANIC, "multixact_redo: unknown op code %u", info);
diff --git a/src/backend/commands/vacuum.c b/src/backend/commands/vacuum.c
index 698bb35..6d55148 100644
--- a/src/backend/commands/vacuum.c
+++ b/src/backend/commands/vacuum.c
@@ -1141,7 +1141,7 @@ vac_truncate_clog(TransactionId frozenXID,
 	 */
 	TruncateCLOG(frozenXID);
 	TruncateCommitTs(frozenXID, true);
-	TruncateMultiXact(minMulti, minmulti_datoid, false);
+	TruncateMultiXact(minMulti, minmulti_datoid);
 
 	/*
 	 * Update the wrap limit for GetNewTransactionId and creation of new
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index 47ef38d..6ef8ba9 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -136,7 +136,7 @@ extern void MultiXactGetCheckptMulti(bool is_shutdown,
 						 Oid *oldestMultiDB);
 extern void CheckPointMultiXact(void);
 extern MultiXactId GetOldestMultiXactId(void);
-extern void TruncateMultiXact(MultiXactId oldestMulti, Oid oldestMultiDB, bool in_recovery);
+extern void TruncateMultiXact(MultiXactId oldestMulti, Oid oldestMultiDB);
 extern void MultiXactSetNextMXact(MultiXactId nextMulti,
 					  MultiXactOffset nextMultiOffset);
 extern void MultiXactAdvanceNextMXact(MultiXactId minMulti,
diff --git a/src/include/access/xlog_internal.h b/src/include/access/xlog_internal.h
index 590bf17..5096c17 100644
--- a/src/include/access/xlog_internal.h
+++ b/src/include/access/xlog_internal.h
@@ -31,7 +31,7 @@
 /*
  * Each page of XLOG file has a header like this:
  */
-#define XLOG_PAGE_MAGIC 0xD086	/* can be used as WAL version indicator */
+#define XLOG_PAGE_MAGIC 0xD087	/* can be used as WAL version indicator */
 
 typedef struct XLogPageHeaderData
 {
-- 
2.5.0.400.gff86faf

>From f8cf132251623a2518f1ff479618bf7ed1363eb3 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Thu, 4 Jun 2015 19:38:32 +0200
Subject: [PATCH 1/3] WIP-dontcommit: Add functions to burn multixacts

This should live in its own module, but we don't have that yet.
---
 contrib/pageinspect/heapfuncs.c          | 43 ++++++++++++++++++++++++++++++++
 contrib/pageinspect/pageinspect--1.3.sql |  6 +++++
 src/backend/access/heap/heapam.c         |  2 +-
 src/backend/access/transam/multixact.c   | 15 ++++++-----
 src/include/access/multixact.h           |  3 ++-
 5 files changed, 61 insertions(+), 8 deletions(-)

diff --git a/contrib/pageinspect/heapfuncs.c b/contrib/pageinspect/heapfuncs.c
index 8d1666c..7a3aa14 100644
--- a/contrib/pageinspect/heapfuncs.c
+++ b/contrib/pageinspect/heapfuncs.c
@@ -29,6 +29,8 @@
 #include "funcapi.h"
 #include "utils/builtins.h"
 #include "miscadmin.h"
+#include "access/multixact.h"
+#include "access/transam.h"
 
 
 /*
@@ -223,3 +225,44 @@ heap_page_items(PG_FUNCTION_ARGS)
 	else
 		SRF_RETURN_DONE(fctx);
 }
+
+extern Datum
+pg_burn_multixact(PG_FUNCTION_ARGS);
+PG_FUNCTION_INFO_V1(pg_burn_multixact);
+
+Datum
+pg_burn_multixact(PG_FUNCTION_ARGS)
+{
+	int		rep = PG_GETARG_INT32(0);
+	int		size = PG_GETARG_INT32(1);
+	MultiXactMember *members;
+	MultiXactId ret;
+	TransactionId id = ReadNewTransactionId() - size;
+	int		i;
+
+	if (rep < 1)
+		elog(ERROR, "need to burn, burn, burn");
+
+	members = palloc(size * sizeof(MultiXactMember));
+	for (i = 0; i < size; i++)
+	{
+		members[i].xid = id++;
+		members[i].status = MultiXactStatusForShare;
+
+		if (!TransactionIdIsNormal(members[i].xid))
+		{
+			id = FirstNormalTransactionId;
+			members[i].xid = id++;
+		}
+	}
+
+	MultiXactIdSetOldestMember();
+
+	for (i = 0; i < rep; i++)
+	{
+		CHECK_FOR_INTERRUPTS();
+		ret = MultiXactIdCreateFromMembers(size, members, true);
+	}
+
+	PG_RETURN_INT64((int64) ret);
+}
diff --git a/contrib/pageinspect/pageinspect--1.3.sql b/contrib/pageinspect/pageinspect--1.3.sql
index a99e058..22f51bc 100644
--- a/contrib/pageinspect/pageinspect--1.3.sql
+++ b/contrib/pageinspect/pageinspect--1.3.sql
@@ -187,3 +187,9 @@ CREATE FUNCTION gin_leafpage_items(IN page bytea,
 RETURNS SETOF record
 AS 'MODULE_PATHNAME', 'gin_leafpage_items'
 LANGUAGE C STRICT;
+
+
+CREATE FUNCTION pg_burn_multixact(num int4, size int4)
+RETURNS int4
+AS 'MODULE_PATHNAME', 'pg_burn_multixact'
+LANGUAGE C STRICT;
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index bcf9871..e167684 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -6099,7 +6099,7 @@ FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
 		 * Create a new multixact with the surviving members of the previous
 		 * one, to set as new Xmax in the tuple.
 		 */
-		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers);
+		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers, false);
 		*flags |= FRM_RETURN_IS_MULTI;
 	}
 
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 1933a87..34c5370 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -407,7 +407,7 @@ MultiXactIdCreate(TransactionId xid1, MultiXactStatus status1,
 	members[1].xid = xid2;
 	members[1].status = status2;
 
-	newMulti = MultiXactIdCreateFromMembers(2, members);
+	newMulti = MultiXactIdCreateFromMembers(2, members, false);
 
 	debug_elog3(DEBUG2, "Create: %s",
 				mxid_to_string(newMulti, 2, members));
@@ -473,7 +473,7 @@ MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
 		 */
 		member.xid = xid;
 		member.status = status;
-		newMulti = MultiXactIdCreateFromMembers(1, &member);
+		newMulti = MultiXactIdCreateFromMembers(1, &member, false);
 
 		debug_elog4(DEBUG2, "Expand: %u has no members, create singleton %u",
 					multi, newMulti);
@@ -525,7 +525,7 @@ MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
 
 	newMembers[j].xid = xid;
 	newMembers[j++].status = status;
-	newMulti = MultiXactIdCreateFromMembers(j, newMembers);
+	newMulti = MultiXactIdCreateFromMembers(j, newMembers, false);
 
 	pfree(members);
 	pfree(newMembers);
@@ -744,7 +744,7 @@ ReadNextMultiXactId(void)
  * NB: the passed members[] array will be sorted in-place.
  */
 MultiXactId
-MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
+MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members, bool nocache)
 {
 	MultiXactId multi;
 	MultiXactOffset offset;
@@ -763,7 +763,9 @@ MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
 	 * corner cases where someone else added us to a MultiXact without our
 	 * knowledge, but it's not worth checking for.)
 	 */
-	multi = mXactCacheGetBySet(nmembers, members);
+	multi = nocache ? InvalidMultiXactId :
+		mXactCacheGetBySet(nmembers, members);
+
 	if (MultiXactIdIsValid(multi))
 	{
 		debug_elog2(DEBUG2, "Create: in cache!");
@@ -836,7 +838,8 @@ MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
 	END_CRIT_SECTION();
 
 	/* Store the new MultiXactId in the local cache, too */
-	mXactCachePut(multi, nmembers, members);
+	if (!nocache)
+		mXactCachePut(multi, nmembers, members);
 
 	debug_elog2(DEBUG2, "Create: all done");
 
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index f1448fe..6213f8a 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -86,10 +86,11 @@ typedef struct xl_multixact_create
 extern MultiXactId MultiXactIdCreate(TransactionId xid1,
 				  MultiXactStatus status1, TransactionId xid2,
 				  MultiXactStatus status2);
+extern MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members, bool nocache);
 extern MultiXactId MultiXactIdExpand(MultiXactId multi, TransactionId xid,
 				  MultiXactStatus status);
 extern MultiXactId MultiXactIdCreateFromMembers(int nmembers,
-							 MultiXactMember *members);
+							 MultiXactMember *members, bool nocache);
 
 extern MultiXactId ReadNextMultiXactId(void);
 extern bool MultiXactIdIsRunning(MultiXactId multi, bool isLockOnly);
-- 
2.5.0.400.gff86faf

>From 436fe7c732d22b1b53b85ddf6e7cf75c1e1ff685 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Tue, 22 Sep 2015 15:17:09 +0200
Subject: [PATCH 2/3] Rework the way multixact truncations work.

The fact that multixact truncations are not WAL logged has caused a fair
share of problems. Amongst others it requires to do computations during
recovery while the database is not in a consistent state, delaying
truncations till checkpoints, and handling members being truncated, but
offset not.

We tried to put bandaids on lots of these issues over the last years,
but it seems time to change course. Thus this patch introduces WAL
logging for truncation, even in the back branches.

This allows:
1) to perform the truncation directly during VACUUM, instead of delaying it
   to the checkpoint.
2) to avoid looking at the offsets SLRU for truncation during recovery,
   we can just use the master's values.
3) simplify a fair amount of logic to keep in memory limits straight,
   this has gotten much easier

During the course of fixing this a bunch of bugs had to be fixed:
1) Data was not purged from memory the member's slru before deleting
   segments. This happened to be hard or impossible to hit due to the
   interlock between checkpoints and truncation.
2) find_multixact_start() relied on SimpleLruDoesPhysicalPageExist - but
   that doesn't work for offsets that haven't yet been flushed to
   disk. Flush out before running to fix. Not pretty, but it feels
   slightly safer to only make decisions based on on-disk state.
3) find_multixact_start() could be called concurrently with a truncation
   and thus fail. Via SetOffsetVacuumLimit() that could lead to a round
   of emergency vacuuming. The problem remains in
   pg_get_multixact_members(), but that's quite harmless.

To handle the case of an updated standby replaying WAL from a not-yet
upgraded primary we have to recognize that situation and use "old style"
truncation (i.e. looking at the SLRUs) during WAL replay. In contrast to
before, this now happens in the startup process, when replaying a
checkpoint record, instead of the checkpointer. Doing this in the
restartpoint was incorrect, they can happen much later than the original
checkpoint, thereby leading to wraparound. It's also more in line to how
the WAL logging now works.

To avoid "multixact_redo: unknown op code 48" errors standbys should be
upgraded before primaries. This needs to be expressed clearly in the
release notes.

WIP: Backpatch to 9.3, where the use of multixacts was expanded. Arguably
this could be backpatched further, but there doesn't seem to be
sufficient benefit to outweigh the risk of applying a significantly
different patch there.

Discussion: 20150621192409.GA4797@alap3.anarazel.de
Reviewed-By: Robert Haas, Alvaro Herrera, Thomas Munro
Backpatch: probably-not-9.3-but-9.5
---
 src/backend/access/rmgrdesc/mxactdesc.c  |  11 +
 src/backend/access/transam/multixact.c   | 700 ++++++++++++++++++-------------
 src/backend/access/transam/slru.c        |  83 +++-
 src/backend/access/transam/xlog.c        |  53 +--
 src/backend/commands/vacuum.c            |   4 +-
 src/backend/storage/lmgr/lwlocknames.txt |   1 +
 src/include/access/multixact.h           |  19 +-
 src/include/access/slru.h                |   4 +-
 src/tools/pgindent/typedefs.list         |   1 +
 9 files changed, 533 insertions(+), 343 deletions(-)

diff --git a/src/backend/access/rmgrdesc/mxactdesc.c b/src/backend/access/rmgrdesc/mxactdesc.c
index 572951e..5b8134f 100644
--- a/src/backend/access/rmgrdesc/mxactdesc.c
+++ b/src/backend/access/rmgrdesc/mxactdesc.c
@@ -70,6 +70,14 @@ multixact_desc(StringInfo buf, XLogReaderState *record)
 		for (i = 0; i < xlrec->nmembers; i++)
 			out_member(buf, &xlrec->members[i]);
 	}
+	else if (info == XLOG_MULTIXACT_TRUNCATE_ID)
+	{
+		xl_multixact_truncate *xlrec = (xl_multixact_truncate *) rec;
+
+		appendStringInfo(buf, "offsets [%u, %u), members [%u, %u)",
+						 xlrec->startTruncOff, xlrec->endTruncOff,
+						 xlrec->startTruncMemb, xlrec->endTruncMemb);
+	}
 }
 
 const char *
@@ -88,6 +96,9 @@ multixact_identify(uint8 info)
 		case XLOG_MULTIXACT_CREATE_ID:
 			id = "CREATE_ID";
 			break;
+		case XLOG_MULTIXACT_TRUNCATE_ID:
+			id = "TRUNCATE_ID";
+			break;
 	}
 
 	return id;
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 34c5370..d19b4c2 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -49,9 +49,7 @@
  * value is removed; the cutoff value is stored in pg_class.  The minimum value
  * across all tables in each database is stored in pg_database, and the global
  * minimum across all databases is part of pg_control and is kept in shared
- * memory.  At checkpoint time, after the value is known flushed in WAL, any
- * files that correspond to multixacts older than that value are removed.
- * (These files are also removed when a restartpoint is executed.)
+ * memory.  Whenever that minimum is advanced, the SLRUs are truncated.
  *
  * When new multixactid values are to be created, care is taken that the
  * counter does not fall within the wraparound horizon considering the global
@@ -83,6 +81,7 @@
 #include "postmaster/autovacuum.h"
 #include "storage/lmgr.h"
 #include "storage/pmsignal.h"
+#include "storage/proc.h"
 #include "storage/procarray.h"
 #include "utils/builtins.h"
 #include "utils/memutils.h"
@@ -109,6 +108,7 @@
 	((xid) / (MultiXactOffset) MULTIXACT_OFFSETS_PER_PAGE)
 #define MultiXactIdToOffsetEntry(xid) \
 	((xid) % (MultiXactOffset) MULTIXACT_OFFSETS_PER_PAGE)
+#define MultiXactIdToOffsetSegment(xid) (MultiXactIdToOffsetPage(xid) / SLRU_PAGES_PER_SEGMENT)
 
 /*
  * The situation for members is a bit more complex: we store one byte of
@@ -153,6 +153,7 @@
 
 /* page in which a member is to be found */
 #define MXOffsetToMemberPage(xid) ((xid) / (TransactionId) MULTIXACT_MEMBERS_PER_PAGE)
+#define MXOffsetToMemberSegment(xid) (MXOffsetToMemberPage(xid) / SLRU_PAGES_PER_SEGMENT)
 
 /* Location (byte offset within page) of flag word for a given member */
 #define MXOffsetToFlagsOffset(xid) \
@@ -212,19 +213,20 @@ typedef struct MultiXactStateData
 	Oid			oldestMultiXactDB;
 
 	/*
-	 * Oldest multixact offset that is potentially referenced by a
-	 * multixact referenced by a relation.  We don't always know this value,
-	 * so there's a flag here to indicate whether or not we currently do.
+	 * Oldest multixact offset that is potentially referenced by a multixact
+	 * referenced by a relation.  We don't always know this value, so there's
+	 * a flag here to indicate whether or not we currently do.
 	 */
 	MultiXactOffset oldestOffset;
 	bool		oldestOffsetKnown;
 
 	/*
-	 * This is what the previous checkpoint stored as the truncate position.
-	 * This value is the oldestMultiXactId that was valid when a checkpoint
-	 * was last executed.
+	 * True if a multixact truncation WAL record was replayed since the last
+	 * checkpoint. This is used to trigger 'legacy truncations', i.e. truncate
+	 * by looking at the data directory during WAL replay, when the primary is
+	 * too old to generate truncation records.
 	 */
-	MultiXactId lastCheckpointedOldest;
+	bool		sawTruncationInCkptCycle;
 
 	/* support for anti-wraparound measures */
 	MultiXactId multiVacLimit;
@@ -233,8 +235,7 @@ typedef struct MultiXactStateData
 	MultiXactId multiWrapLimit;
 
 	/* support for members anti-wraparound measures */
-	MultiXactOffset offsetStopLimit;
-	bool offsetStopLimitKnown;
+	MultiXactOffset offsetStopLimit;	/* known if oldestOffsetKnown */
 
 	/*
 	 * Per-backend data starts here.  We have two arrays stored in the area
@@ -364,12 +365,14 @@ static bool MultiXactOffsetPrecedes(MultiXactOffset offset1,
 						MultiXactOffset offset2);
 static void ExtendMultiXactOffset(MultiXactId multi);
 static void ExtendMultiXactMember(MultiXactOffset offset, int nmembers);
-static void DetermineSafeOldestOffset(MultiXactId oldestMXact);
 static bool MultiXactOffsetWouldWrap(MultiXactOffset boundary,
 						 MultiXactOffset start, uint32 distance);
-static bool SetOffsetVacuumLimit(bool finish_setup);
+static bool SetOffsetVacuumLimit(void);
 static bool find_multixact_start(MultiXactId multi, MultiXactOffset *result);
 static void WriteMZeroPageXlogRec(int pageno, uint8 info);
+static void WriteMTruncateXlogRec(Oid oldestMultiDB,
+					  MultiXactId startOff, MultiXactId endOff,
+					  MultiXactOffset startMemb, MultiXactOffset endMemb);
 
 
 /*
@@ -1102,7 +1105,7 @@ GetNewMultiXactId(int nmembers, MultiXactOffset *offset)
 	 *----------
 	 */
 #define OFFSET_WARN_SEGMENTS	20
-	if (MultiXactState->offsetStopLimitKnown &&
+	if (MultiXactState->oldestOffsetKnown &&
 		MultiXactOffsetWouldWrap(MultiXactState->offsetStopLimit, nextOffset,
 								 nmembers))
 	{
@@ -1142,7 +1145,7 @@ GetNewMultiXactId(int nmembers, MultiXactOffset *offset)
 			SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
 	}
 
-	if (MultiXactState->offsetStopLimitKnown &&
+	if (MultiXactState->oldestOffsetKnown &&
 		MultiXactOffsetWouldWrap(MultiXactState->offsetStopLimit,
 								 nextOffset,
 								 nmembers + MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT * OFFSET_WARN_SEGMENTS))
@@ -2013,20 +2016,24 @@ StartupMultiXact(void)
 
 /*
  * This must be called ONCE at the end of startup/recovery.
- *
- * We don't need any locks here, really; the SLRU locks are taken only because
- * slru.c expects to be called with locks held.
  */
 void
 TrimMultiXact(void)
 {
-	MultiXactId multi = MultiXactState->nextMXact;
-	MultiXactOffset offset = MultiXactState->nextOffset;
-	MultiXactId	oldestMXact;
+	MultiXactId nextMXact;
+	MultiXactOffset offset;
+	MultiXactId oldestMXact;
+	Oid			oldestMXactDB;
 	int			pageno;
 	int			entryno;
 	int			flagsoff;
 
+	LWLockAcquire(MultiXactGenLock, LW_SHARED);
+	nextMXact = MultiXactState->nextMXact;
+	offset = MultiXactState->nextOffset;
+	oldestMXact = MultiXactState->oldestMultiXactId;
+	oldestMXactDB = MultiXactState->oldestMultiXactDB;
+	LWLockRelease(MultiXactGenLock);
 
 	/* Clean up offsets state */
 	LWLockAcquire(MultiXactOffsetControlLock, LW_EXCLUSIVE);
@@ -2034,20 +2041,20 @@ TrimMultiXact(void)
 	/*
 	 * (Re-)Initialize our idea of the latest page number for offsets.
 	 */
-	pageno = MultiXactIdToOffsetPage(multi);
+	pageno = MultiXactIdToOffsetPage(nextMXact);
 	MultiXactOffsetCtl->shared->latest_page_number = pageno;
 
 	/*
 	 * Zero out the remainder of the current offsets page.  See notes in
 	 * TrimCLOG() for motivation.
 	 */
-	entryno = MultiXactIdToOffsetEntry(multi);
+	entryno = MultiXactIdToOffsetEntry(nextMXact);
 	if (entryno != 0)
 	{
 		int			slotno;
 		MultiXactOffset *offptr;
 
-		slotno = SimpleLruReadPage(MultiXactOffsetCtl, pageno, true, multi);
+		slotno = SimpleLruReadPage(MultiXactOffsetCtl, pageno, true, nextMXact);
 		offptr = (MultiXactOffset *) MultiXactOffsetCtl->shared->page_buffer[slotno];
 		offptr += entryno;
 
@@ -2096,12 +2103,13 @@ TrimMultiXact(void)
 
 	LWLockRelease(MultiXactMemberControlLock);
 
-	if (SetOffsetVacuumLimit(true) && IsUnderPostmaster)
-		SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	oldestMXact = MultiXactState->lastCheckpointedOldest;
+	/* signal that we're officially up */
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	MultiXactState->finishedStartup = true;
 	LWLockRelease(MultiXactGenLock);
-	DetermineSafeOldestOffset(oldestMXact);
+
+	/* Now compute how far away the next members wraparound is. */
+	SetMultiXactIdLimit(oldestMXact, oldestMXactDB);
 }
 
 /*
@@ -2270,8 +2278,20 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 	 (errmsg("MultiXactId wrap limit is %u, limited by database with OID %u",
 			 multiWrapLimit, oldest_datoid)));
 
+	/*
+	 * Computing the actual limits is only possible once the data directory is
+	 * in a consistent state. There's no need to compute the limits while
+	 * still replaying WAL - no decisions about new multis are made even
+	 * though multixact creations might be replayed. So we'll only do further
+	 * checks after TrimMultiXact() has been called.
+	 */
+	if (!MultiXactState->finishedStartup)
+		return;
+
+	Assert(!InRecovery);
+
 	/* Set limits for offset vacuum. */
-	needs_offset_vacuum = SetOffsetVacuumLimit(false);
+	needs_offset_vacuum = SetOffsetVacuumLimit();
 
 	/*
 	 * If past the autovacuum force point, immediately signal an autovac
@@ -2281,11 +2301,11 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 	 * another iteration immediately if there are still any old databases.
 	 */
 	if ((MultiXactIdPrecedes(multiVacLimit, curMulti) ||
-		 needs_offset_vacuum) && IsUnderPostmaster && !InRecovery)
+		 needs_offset_vacuum) && IsUnderPostmaster)
 		SendPostmasterSignal(PMSIGNAL_START_AUTOVAC_LAUNCHER);
 
 	/* Give an immediate warning if past the wrap warn point */
-	if (MultiXactIdPrecedes(multiWarnLimit, curMulti) && !InRecovery)
+	if (MultiXactIdPrecedes(multiWarnLimit, curMulti))
 	{
 		char	   *oldest_datname;
 
@@ -2353,27 +2373,39 @@ MultiXactAdvanceNextMXact(MultiXactId minMulti,
 }
 
 /*
- * Update our oldestMultiXactId value, but only if it's more recent than
- * what we had.  However, even if not, always update the oldest multixact
- * offset limit.
+ * Update our oldestMultiXactId value, but only if it's more recent than what
+ * we had.
+ *
+ * This may only be called during WAL replay.
  */
 void
 MultiXactAdvanceOldest(MultiXactId oldestMulti, Oid oldestMultiDB)
 {
+	Assert(InRecovery);
+
 	if (MultiXactIdPrecedes(MultiXactState->oldestMultiXactId, oldestMulti))
+	{
+		/*
+		 * If there has been a truncation on the master, detected by seeing a
+		 * moving oldestMulti, without a corresponding truncation record, we
+		 * know that the primary is still running an older version of postgres
+		 * that doesn't yet log multixact truncations. So perform the
+		 * truncation ourselves.
+		 */
+		if (!MultiXactState->sawTruncationInCkptCycle)
+		{
+			ereport(LOG,
+					(errmsg("performing legacy multixact truncation"),
+					 errdetail("Legacy truncations are sometimes performed when replaying WAL from an older primary."),
+					 errhint("Upgrade the primary, it is susceptible to data corruption.")));
+			TruncateMultiXact(oldestMulti, oldestMultiDB, true);
+		}
+
 		SetMultiXactIdLimit(oldestMulti, oldestMultiDB);
-}
+	}
 
-/*
- * Update the "safe truncation point".  This is the newest value of oldestMulti
- * that is known to be flushed as part of a checkpoint record.
- */
-void
-MultiXactSetSafeTruncate(MultiXactId safeTruncateMulti)
-{
-	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-	MultiXactState->lastCheckpointedOldest = safeTruncateMulti;
-	LWLockRelease(MultiXactGenLock);
+	/* only looked at in the startup process, no lock necessary */
+	MultiXactState->sawTruncationInCkptCycle = false;
 }
 
 /*
@@ -2529,132 +2561,56 @@ GetOldestMultiXactId(void)
 }
 
 /*
- * Based on the given oldest MultiXactId, determine what's the oldest member
- * offset and install the limit info in MultiXactState, where it can be used to
- * prevent overrun of old data in the members SLRU area.
- */
-static void
-DetermineSafeOldestOffset(MultiXactId oldestMXact)
-{
-	MultiXactOffset oldestOffset;
-	MultiXactOffset nextOffset;
-	MultiXactOffset offsetStopLimit;
-	MultiXactOffset prevOffsetStopLimit;
-	MultiXactId		nextMXact;
-	bool			finishedStartup;
-	bool			prevOffsetStopLimitKnown;
-
-	/* Fetch values from shared memory. */
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	finishedStartup = MultiXactState->finishedStartup;
-	nextMXact = MultiXactState->nextMXact;
-	nextOffset = MultiXactState->nextOffset;
-	prevOffsetStopLimit = MultiXactState->offsetStopLimit;
-	prevOffsetStopLimitKnown = MultiXactState->offsetStopLimitKnown;
-	LWLockRelease(MultiXactGenLock);
-
-	/* Don't worry about this until after we've started up. */
-	if (!finishedStartup)
-		return;
-
-	/*
-	 * Determine the offset of the oldest multixact.  Normally, we can read
-	 * the offset from the multixact itself, but there's an important special
-	 * case: if there are no multixacts in existence at all, oldestMXact
-	 * obviously can't point to one.  It will instead point to the multixact
-	 * ID that will be assigned the next time one is needed.
-	 *
-	 * NB: oldestMXact should be the oldest multixact that still exists in the
-	 * SLRU, unlike in SetOffsetVacuumLimit, where we do this same computation
-	 * based on the oldest value that might be referenced in a table.
-	 */
-	if (nextMXact == oldestMXact)
-		oldestOffset = nextOffset;
-	else
-	{
-		bool		oldestOffsetKnown;
-
-		oldestOffsetKnown = find_multixact_start(oldestMXact, &oldestOffset);
-		if (!oldestOffsetKnown)
-		{
-			ereport(LOG,
-					(errmsg("MultiXact member wraparound protections are disabled because oldest checkpointed MultiXact %u does not exist on disk",
-						oldestMXact)));
-			return;
-		}
-	}
-
-	/* move back to start of the corresponding segment */
-	offsetStopLimit = oldestOffset - (oldestOffset %
-		(MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT));
-	/* always leave one segment before the wraparound point */
-	offsetStopLimit -= (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT);
-
-	/* if nothing has changed, we're done */
-	if (prevOffsetStopLimitKnown && offsetStopLimit == prevOffsetStopLimit)
-		return;
-
-	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-	MultiXactState->offsetStopLimit = offsetStopLimit;
-	MultiXactState->offsetStopLimitKnown = true;
-	LWLockRelease(MultiXactGenLock);
-
-	if (!prevOffsetStopLimitKnown && IsUnderPostmaster)
-		ereport(LOG,
-				(errmsg("MultiXact member wraparound protections are now enabled")));
-	ereport(DEBUG1,
-			(errmsg("MultiXact member stop limit is now %u based on MultiXact %u",
-				offsetStopLimit, oldestMXact)));
-}
-
-/*
  * Determine how aggressively we need to vacuum in order to prevent member
  * wraparound.
  *
- * To determine the oldest multixact ID, we look at oldestMultiXactId, not
- * lastCheckpointedOldest.  That's because vacuuming can't help with anything
- * older than oldestMultiXactId; anything older than that isn't referenced
- * by any table.  Offsets older than oldestMultiXactId but not as old as
- * lastCheckpointedOldest will go away after the next checkpoint.
+ * To do so determine what's the oldest member offset and install the limit
+ * info in MultiXactState, where it can be used to prevent overrun of old data
+ * in the members SLRU area.
  *
  * The return value is true if emergency autovacuum is required and false
  * otherwise.
  */
 static bool
-SetOffsetVacuumLimit(bool finish_setup)
+SetOffsetVacuumLimit(void)
 {
-	MultiXactId	oldestMultiXactId;
+	MultiXactId oldestMultiXactId;
 	MultiXactId nextMXact;
-	bool		finishedStartup;
-	MultiXactOffset oldestOffset = 0;		/* placate compiler */
+	MultiXactOffset oldestOffset = 0;	/* placate compiler */
+	MultiXactOffset prevOldestOffset;
 	MultiXactOffset nextOffset;
 	bool		oldestOffsetKnown = false;
-	MultiXactOffset prevOldestOffset;
 	bool		prevOldestOffsetKnown;
+	MultiXactOffset offsetStopLimit = 0;
+
+	/*
+	 * NB: Have to prevent concurrent truncation, we might otherwise try to
+	 * lookup a oldestMulti that's concurrently getting truncated away.
+	 */
+	LWLockAcquire(MultiXactTruncationLock, LW_SHARED);
 
 	/* Read relevant fields from shared memory. */
 	LWLockAcquire(MultiXactGenLock, LW_SHARED);
 	oldestMultiXactId = MultiXactState->oldestMultiXactId;
 	nextMXact = MultiXactState->nextMXact;
 	nextOffset = MultiXactState->nextOffset;
-	finishedStartup = MultiXactState->finishedStartup;
-	prevOldestOffset = MultiXactState->oldestOffset;
 	prevOldestOffsetKnown = MultiXactState->oldestOffsetKnown;
+	prevOldestOffset = MultiXactState->oldestOffset;
+	Assert(MultiXactState->finishedStartup);
 	LWLockRelease(MultiXactGenLock);
 
-	/* Don't do this until after any recovery is complete. */
-	if (!finishedStartup && !finish_setup)
-		return false;
-
 	/*
-	 * If no multixacts exist, then oldestMultiXactId will be the next
-	 * multixact that will be created, rather than an existing multixact.
+	 * Determine the offset of the oldest multixact.  Normally, we can read
+	 * the offset from the multixact itself, but there's an important special
+	 * case: if there are no multixacts in existence at all, oldestMXact
+	 * obviously can't point to one.  It will instead point to the multixact
+	 * ID that will be assigned the next time one is needed.
 	 */
 	if (oldestMultiXactId == nextMXact)
 	{
 		/*
-		 * When the next multixact gets created, it will be stored at the
-		 * next offset.
+		 * When the next multixact gets created, it will be stored at the next
+		 * offset.
 		 */
 		oldestOffset = nextOffset;
 		oldestOffsetKnown = true;
@@ -2662,55 +2618,67 @@ SetOffsetVacuumLimit(bool finish_setup)
 	else
 	{
 		/*
-		 * Figure out where the oldest existing multixact's offsets are stored.
-		 * Due to bugs in early release of PostgreSQL 9.3.X and 9.4.X, the
-		 * supposedly-earliest multixact might not really exist.  We are
+		 * Figure out where the oldest existing multixact's offsets are
+		 * stored. Due to bugs in early release of PostgreSQL 9.3.X and 9.4.X,
+		 * the supposedly-earliest multixact might not really exist.  We are
 		 * careful not to fail in that case.
 		 */
 		oldestOffsetKnown =
 			find_multixact_start(oldestMultiXactId, &oldestOffset);
-	}
 
-	/*
-	 * Except when initializing the system for the first time, there's no
-	 * need to update anything if we don't know the oldest offset or if it
-	 * hasn't changed.
-	 */
-	if (finish_setup ||
-		(oldestOffsetKnown && !prevOldestOffsetKnown) ||
-		(oldestOffsetKnown && prevOldestOffset != oldestOffset))
-	{
-		/* Install the new limits. */
-		LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
-		MultiXactState->oldestOffset = oldestOffset;
-		MultiXactState->oldestOffsetKnown = oldestOffsetKnown;
-		MultiXactState->finishedStartup = true;
-		LWLockRelease(MultiXactGenLock);
-
-		/* Log the info */
 		if (oldestOffsetKnown)
 			ereport(DEBUG1,
 					(errmsg("oldest MultiXactId member is at offset %u",
-						oldestOffset)));
+							oldestOffset)));
 		else
-			ereport(DEBUG1,
-					(errmsg("oldest MultiXactId member offset unknown")));
+			ereport(LOG,
+					(errmsg("MultiXact member wraparound protections are disabled because oldest checkpointed MultiXact %u does not exist on disk",
+							oldestMultiXactId)));
 	}
 
+	LWLockRelease(MultiXactTruncationLock);
+
 	/*
-	 * If we failed to get the oldest offset this time, but we have a value
-	 * from a previous pass through this function, assess the need for
-	 * autovacuum based on that old value rather than automatically forcing
-	 * it.
+	 * If we can, compute limits (and install them MultiXactState) to prevent
+	 * overrun of old data in the members SLRU area. We can only do so if the
+	 * oldest offset is known though.
 	 */
-	if (prevOldestOffsetKnown && !oldestOffsetKnown)
+	if (oldestOffsetKnown)
+	{
+		/* move back to start of the corresponding segment */
+		offsetStopLimit = oldestOffset - (oldestOffset %
+					  (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT));
+
+		/* always leave one segment before the wraparound point */
+		offsetStopLimit -= (MULTIXACT_MEMBERS_PER_PAGE * SLRU_PAGES_PER_SEGMENT);
+
+		if (!prevOldestOffsetKnown && IsUnderPostmaster)
+			ereport(LOG,
+					(errmsg("MultiXact member wraparound protections are now enabled")));
+		ereport(DEBUG1,
+		(errmsg("MultiXact member stop limit is now %u based on MultiXact %u",
+				offsetStopLimit, oldestMultiXactId)));
+	}
+	else if (prevOldestOffsetKnown)
 	{
+		/*
+		 * If we failed to get the oldest offset this time, but we have a
+		 * value from a previous pass through this function, use the old value
+		 * rather than automatically forcing it.
+		 */
 		oldestOffset = prevOldestOffset;
 		oldestOffsetKnown = true;
 	}
 
+	/* Install the computed values */
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	MultiXactState->oldestOffset = oldestOffset;
+	MultiXactState->oldestOffsetKnown = oldestOffsetKnown;
+	MultiXactState->offsetStopLimit = offsetStopLimit;
+	LWLockRelease(MultiXactGenLock);
+
 	/*
-	 * Do we need an emergency autovacuum?  If we're not sure, assume yes.
+	 * Do we need an emergency autovacuum?	If we're not sure, assume yes.
 	 */
 	return !oldestOffsetKnown ||
 		(nextOffset - oldestOffset > MULTIXACT_MEMBER_SAFE_THRESHOLD);
@@ -2723,7 +2691,7 @@ SetOffsetVacuumLimit(bool finish_setup)
  * boundary point, hence the name.  The reason we don't want to use the regular
  * 2^31-modulo arithmetic here is that we want to be able to use the whole of
  * the 2^32-1 space here, allowing for more multixacts that would fit
- * otherwise.  See also SlruScanDirCbRemoveMembers.
+ * otherwise.
  */
 static bool
 MultiXactOffsetWouldWrap(MultiXactOffset boundary, MultiXactOffset start,
@@ -2769,6 +2737,9 @@ MultiXactOffsetWouldWrap(MultiXactOffset boundary, MultiXactOffset start,
  *
  * Returns false if the file containing the multi does not exist on disk.
  * Otherwise, returns true and sets *result to the starting member offset.
+ *
+ * This function does not prevent concurrent truncation, so if that's
+ * required, the caller has to protect against that.
  */
 static bool
 find_multixact_start(MultiXactId multi, MultiXactOffset *result)
@@ -2779,9 +2750,22 @@ find_multixact_start(MultiXactId multi, MultiXactOffset *result)
 	int			slotno;
 	MultiXactOffset *offptr;
 
+	/* XXX: Remove || AmStartupProcess() after WAL page magic bump */
+	Assert(MultiXactState->finishedStartup || AmStartupProcess());
+
 	pageno = MultiXactIdToOffsetPage(multi);
 	entryno = MultiXactIdToOffsetEntry(multi);
 
+	/*
+	 * We need to flush out dirty data, so PhysicalPageExists can work
+	 * correctly, but SimpleLruFlush() is a pretty big hammer for that.
+	 * Alternatively we could add a in-memory version of page exists, but
+	 * find_multixact_start is called infrequently, and it doesn't seem bad to
+	 * flush buffers to disk before truncation.
+	 */
+	SimpleLruFlush(MultiXactOffsetCtl, true);
+	SimpleLruFlush(MultiXactMemberCtl, true);
+
 	if (!SimpleLruDoesPhysicalPageExist(MultiXactOffsetCtl, pageno))
 		return false;
 
@@ -2887,65 +2871,6 @@ MultiXactMemberFreezeThreshold(void)
 	return multixacts - victim_multixacts;
 }
 
-/*
- * SlruScanDirectory callback.
- *		This callback deletes segments that are outside the range determined by
- *		the given page numbers.
- *
- * Both range endpoints are exclusive (that is, segments containing any of
- * those pages are kept.)
- */
-typedef struct MembersLiveRange
-{
-	int			rangeStart;
-	int			rangeEnd;
-} MembersLiveRange;
-
-static bool
-SlruScanDirCbRemoveMembers(SlruCtl ctl, char *filename, int segpage,
-						   void *data)
-{
-	MembersLiveRange *range = (MembersLiveRange *) data;
-	MultiXactOffset nextOffset;
-
-	if ((segpage == range->rangeStart) ||
-		(segpage == range->rangeEnd))
-		return false;			/* easy case out */
-
-	/*
-	 * To ensure that no segment is spuriously removed, we must keep track of
-	 * new segments added since the start of the directory scan; to do this,
-	 * we update our end-of-range point as we run.
-	 *
-	 * As an optimization, we can skip looking at shared memory if we know for
-	 * certain that the current segment must be kept.  This is so because
-	 * nextOffset never decreases, and we never increase rangeStart during any
-	 * one run.
-	 */
-	if (!((range->rangeStart > range->rangeEnd &&
-		   segpage > range->rangeEnd && segpage < range->rangeStart) ||
-		  (range->rangeStart < range->rangeEnd &&
-		   (segpage < range->rangeStart || segpage > range->rangeEnd))))
-		return false;
-
-	/*
-	 * Update our idea of the end of the live range.
-	 */
-	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	nextOffset = MultiXactState->nextOffset;
-	LWLockRelease(MultiXactGenLock);
-	range->rangeEnd = MXOffsetToMemberPage(nextOffset);
-
-	/* Recheck the deletion condition.  If it still holds, perform deletion */
-	if ((range->rangeStart > range->rangeEnd &&
-		 segpage > range->rangeEnd && segpage < range->rangeStart) ||
-		(range->rangeStart < range->rangeEnd &&
-		 (segpage < range->rangeStart || segpage > range->rangeEnd)))
-		SlruDeleteSegment(ctl, filename);
-
-	return false;				/* keep going */
-}
-
 typedef struct mxtruncinfo
 {
 	int			earliestExistingPage;
@@ -2969,37 +2894,110 @@ SlruScanDirCbFindEarliest(SlruCtl ctl, char *filename, int segpage, void *data)
 	return false;				/* keep going */
 }
 
+
+/*
+ * Delete members segments [oldest, newOldest)
+ */
+static void
+PerformMembersTruncation(MultiXactOffset oldestOffset, MultiXactOffset newOldestOffset)
+{
+	const int	maxsegment = MXOffsetToMemberSegment(MaxMultiXactOffset);
+	int			startsegment = MXOffsetToMemberSegment(oldestOffset);
+	int			endsegment = MXOffsetToMemberSegment(newOldestOffset);
+	int			segment = startsegment;
+
+	/*
+	 * Delete all the segments but the last one. The last segment can still
+	 * contain, possibly partially, valid data.
+	 */
+	while (segment != endsegment)
+	{
+		elog(DEBUG2, "truncating multixact members segment %x", segment);
+		SlruDeleteSegment(MultiXactMemberCtl, segment);
+
+		/* move to next segment, handling wraparound correctly */
+		if (segment == maxsegment)
+			segment = 0;
+		else
+			segment += 1;
+	}
+}
+
+/*
+ * Delete offsets segments [oldest, newOldest)
+ */
+static void
+PerformOffsetsTruncation(MultiXactId oldestMulti, MultiXactId newOldestMulti)
+{
+	/*
+	 * We step back one multixact to avoid passing a cutoff page that hasn't
+	 * been created yet in the rare case that oldestMulti would be the first
+	 * item on a page and oldestMulti == nextMulti.  In that case, if we
+	 * didn't subtract one, we'd trigger SimpleLruTruncate's wraparound
+	 * detection.
+	 */
+	SimpleLruTruncate(MultiXactOffsetCtl,
+			   MultiXactIdToOffsetPage(PreviousMultiXactId(newOldestMulti)));
+}
+
 /*
  * Remove all MultiXactOffset and MultiXactMember segments before the oldest
  * ones still of interest.
  *
- * On a primary, this is called by the checkpointer process after a checkpoint
- * has been flushed; during crash recovery, it's called from
- * CreateRestartPoint().  In the latter case, we rely on the fact that
- * xlog_redo() will already have called MultiXactAdvanceOldest().  Our
- * latest_page_number will already have been initialized by StartupMultiXact()
- * and kept up to date as new pages are zeroed.
+ * On a primary this is called as part of vacuum (via
+ * vac_truncate_clog()). During recovery truncation is normally done by
+ * replaying truncation WAL records instead of this routine; the exception is
+ * when replaying records from an older primary that doesn't yet generate
+ * truncation WAL records. In that case truncation is triggered by
+ * MultiXactAdvanceOldest().
+ *
+ * newOldestMulti is the oldest currently required multixact, newOldestMultiDB
+ * is one of the databases preventing newOldestMulti from increasing.
  */
 void
-TruncateMultiXact(void)
+TruncateMultiXact(MultiXactId newOldestMulti, Oid newOldestMultiDB, bool in_recovery)
 {
-	MultiXactId oldestMXact;
+	MultiXactId oldestMulti;
+	MultiXactId nextMulti;
+	MultiXactOffset newOldestOffset;
 	MultiXactOffset oldestOffset;
-	MultiXactId		nextMXact;
-	MultiXactOffset	nextOffset;
+	MultiXactOffset nextOffset;
 	mxtruncinfo trunc;
 	MultiXactId earliest;
-	MembersLiveRange range;
 
-	Assert(AmCheckpointerProcess() || AmStartupProcess() ||
-		   !IsPostmasterEnvironment);
+	/*
+	 * Need to allow being called in recovery for backwards compatibility,
+	 * when an updated standby replays WAL generated by a non-updated primary.
+	 */
+	Assert(in_recovery || !RecoveryInProgress());
+	Assert(!in_recovery || AmStartupProcess());
+	Assert(in_recovery || MultiXactState->finishedStartup);
+
+	/*
+	 * We can only allow one truncation to happen at once. Otherwise parts of
+	 * members might vanish while we're doing lookups or similar. There's no
+	 * need to have an interlock with creating new multis or such, since those
+	 * are constrained by the limits (which only grow, never shrink).
+	 */
+	LWLockAcquire(MultiXactTruncationLock, LW_EXCLUSIVE);
 
 	LWLockAcquire(MultiXactGenLock, LW_SHARED);
-	oldestMXact = MultiXactState->lastCheckpointedOldest;
-	nextMXact = MultiXactState->nextMXact;
+	nextMulti = MultiXactState->nextMXact;
 	nextOffset = MultiXactState->nextOffset;
+	oldestMulti = MultiXactState->oldestMultiXactId;
 	LWLockRelease(MultiXactGenLock);
-	Assert(MultiXactIdIsValid(oldestMXact));
+	Assert(MultiXactIdIsValid(oldestMulti));
+
+	/*
+	 * Make sure to only attempt truncation if there's values to truncate
+	 * away. In normal processing values shouldn't go backwards, but there's
+	 * some corner cases (due to bugs) where that's possible.
+	 */
+	if (MultiXactIdPrecedesOrEquals(newOldestMulti, oldestMulti))
+	{
+		LWLockRelease(MultiXactTruncationLock);
+		return;
+	}
 
 	/*
 	 * Note we can't just plow ahead with the truncation; it's possible that
@@ -3007,6 +3005,9 @@ TruncateMultiXact(void)
 	 * going to attempt to read the offsets page to determine where to
 	 * truncate the members SLRU.  So we first scan the directory to determine
 	 * the earliest offsets page number that we can read without error.
+	 *
+	 * NB: It's also possible that the page that oldestMulti is on has already
+	 * been truncated away, and we crashed before updating oldestMulti.
 	 */
 	trunc.earliestExistingPage = -1;
 	SlruScanDirectory(MultiXactOffsetCtl, SlruScanDirCbFindEarliest, &trunc);
@@ -3014,19 +3015,10 @@ TruncateMultiXact(void)
 	if (earliest < FirstMultiXactId)
 		earliest = FirstMultiXactId;
 
-	/*
-	 * If there's nothing to remove, we can bail out early.
-	 *
-	 * Due to bugs in early releases of PostgreSQL 9.3.X and 9.4.X,
-	 * oldestMXact might point to a multixact that does not exist.
-	 * Autovacuum will eventually advance it to a value that does exist,
-	 * and we want to set a proper offsetStopLimit when that happens,
-	 * so call DetermineSafeOldestOffset here even if we're not actually
-	 * truncating.
-	 */
-	if (MultiXactIdPrecedes(oldestMXact, earliest))
+	/* If there's nothing to remove, we can bail out early. */
+	if (MultiXactIdPrecedes(oldestMulti, earliest))
 	{
-		DetermineSafeOldestOffset(oldestMXact);
+		LWLockRelease(MultiXactTruncationLock);
 		return;
 	}
 
@@ -3035,49 +3027,104 @@ TruncateMultiXact(void)
 	 * the starting offset of the oldest multixact.
 	 *
 	 * Hopefully, find_multixact_start will always work here, because we've
-	 * already checked that it doesn't precede the earliest MultiXact on
-	 * disk.  But if it fails, don't truncate anything, and log a message.
+	 * already checked that it doesn't precede the earliest MultiXact on disk.
+	 * But if it fails, don't truncate anything, and log a message.
 	 */
-	if (oldestMXact == nextMXact)
-		oldestOffset = nextOffset;		/* there are NO MultiXacts */
-	else if (!find_multixact_start(oldestMXact, &oldestOffset))
+	if (oldestMulti == nextMulti)
+	{
+		/* there are NO MultiXacts */
+		oldestOffset = nextOffset;
+	}
+	else if (!find_multixact_start(oldestMulti, &oldestOffset))
 	{
 		ereport(LOG,
 				(errmsg("oldest MultiXact %u not found, earliest MultiXact %u, skipping truncation",
-					oldestMXact, earliest)));
+						oldestMulti, earliest)));
+		LWLockRelease(MultiXactTruncationLock);
 		return;
 	}
 
 	/*
-	 * To truncate MultiXactMembers, we need to figure out the active page
-	 * range and delete all files outside that range.  The start point is the
-	 * start of the segment containing the oldest offset; an end point of the
-	 * segment containing the next offset to use is enough.  The end point is
-	 * updated as MultiXactMember gets extended concurrently, elsewhere.
+	 * Secondly compute up to where to truncate. Lookup the corresponding
+	 * member offset for newOldestMulti for that.
 	 */
-	range.rangeStart = MXOffsetToMemberPage(oldestOffset);
-	range.rangeStart -= range.rangeStart % SLRU_PAGES_PER_SEGMENT;
-
-	range.rangeEnd = MXOffsetToMemberPage(nextOffset);
+	if (newOldestMulti == nextMulti)
+	{
+		/* there are NO MultiXacts */
+		newOldestOffset = nextOffset;
+	}
+	else if (!find_multixact_start(newOldestMulti, &newOldestOffset))
+	{
+		ereport(LOG,
+				(errmsg("cannot truncate up to MultiXact %u because it does not exist on disk, skipping truncation",
+						newOldestMulti)));
+		LWLockRelease(MultiXactTruncationLock);
+		return;
+	}
 
-	SlruScanDirectory(MultiXactMemberCtl, SlruScanDirCbRemoveMembers, &range);
+	elog(DEBUG1, "performing multixact truncation: "
+		 "offsets [%u, %u), offsets segments [%x, %x), "
+		 "members [%u, %u), members segments [%x, %x)",
+		 oldestMulti, newOldestMulti,
+		 MultiXactIdToOffsetSegment(oldestMulti),
+		 MultiXactIdToOffsetSegment(newOldestMulti),
+		 oldestOffset, newOldestOffset,
+		 MXOffsetToMemberSegment(oldestOffset),
+		 MXOffsetToMemberSegment(newOldestOffset));
 
 	/*
-	 * Now we can truncate MultiXactOffset.  We step back one multixact to
-	 * avoid passing a cutoff page that hasn't been created yet in the rare
-	 * case that oldestMXact would be the first item on a page and oldestMXact
-	 * == nextMXact.  In that case, if we didn't subtract one, we'd trigger
-	 * SimpleLruTruncate's wraparound detection.
+	 * Do truncation, and the WAL logging of the truncation, in a critical
+	 * section. That way offsets/members cannot get out of sync anymore, i.e.
+	 * once consistent the newOldestMulti will always exist in members, even
+	 * if we crashed in the wrong moment.
 	 */
-	SimpleLruTruncate(MultiXactOffsetCtl,
-				  MultiXactIdToOffsetPage(PreviousMultiXactId(oldestMXact)));
+	START_CRIT_SECTION();
 
 	/*
-	 * Now, and only now, we can advance the stop point for multixact members.
-	 * If we did it any sooner, the segments we deleted above might already
-	 * have been overwritten with new members.  That would be bad.
+	 * Prevent checkpoints from being scheduled concurrently. This is critical
+	 * because otherwise a truncation record might not be replayed after a
+	 * crash/basebackup, even though the state of the data directory would
+	 * require it.  It's not possible (startup process doesn't have a PGXACT
+	 * entry), and not needed, to do this during recovery, when performing an
+	 * old-style truncation, though. There the entire scheduling depends on
+	 * the replayed WAL records which be the same after a possible crash.
+	 */
+	if (!in_recovery)
+	{
+		Assert(!MyPgXact->delayChkpt);
+		MyPgXact->delayChkpt = true;
+	}
+
+	/* WAL log truncation */
+	if (!in_recovery)
+		WriteMTruncateXlogRec(newOldestMultiDB,
+							  oldestMulti, newOldestMulti,
+							  oldestOffset, newOldestOffset);
+
+	/*
+	 * Update in-memory limits before performing the truncation, while inside
+	 * the critical section: Have to do it before truncation, to prevent
+	 * concurrent lookups of those values. Has to be inside the critical
+	 * section as otherwise a future call to this function would error out,
+	 * while looking up the oldest member in offsets, if our caller crashes
+	 * before updating the limits.
 	 */
-	DetermineSafeOldestOffset(oldestMXact);
+	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
+	MultiXactState->oldestMultiXactId = newOldestMulti;
+	MultiXactState->oldestMultiXactDB = newOldestMultiDB;
+	LWLockRelease(MultiXactGenLock);
+
+	/* First truncate members */
+	PerformMembersTruncation(oldestOffset, newOldestOffset);
+
+	/* Then offsets */
+	PerformOffsetsTruncation(oldestMulti, newOldestMulti);
+
+	if (!in_recovery)
+		MyPgXact->delayChkpt = false;
+
+	END_CRIT_SECTION();
+	LWLockRelease(MultiXactTruncationLock);
 }
 
 /*
@@ -3174,6 +3221,34 @@ WriteMZeroPageXlogRec(int pageno, uint8 info)
 }
 
 /*
+ * Write a TRUNCATE xlog record
+ *
+ * We must flush the xlog record to disk before returning --- see notes in
+ * TruncateCLOG().
+ */
+static void
+WriteMTruncateXlogRec(Oid oldestMultiDB,
+					  MultiXactId startTruncOff, MultiXactId endTruncOff,
+				MultiXactOffset startTruncMemb, MultiXactOffset endTruncMemb)
+{
+	XLogRecPtr	recptr;
+	xl_multixact_truncate xlrec;
+
+	xlrec.oldestMultiDB = oldestMultiDB;
+
+	xlrec.startTruncOff = startTruncOff;
+	xlrec.endTruncOff = endTruncOff;
+
+	xlrec.startTruncMemb = startTruncMemb;
+	xlrec.endTruncMemb = endTruncMemb;
+
+	XLogBeginInsert();
+	XLogRegisterData((char *) (&xlrec), SizeOfMultiXactTruncate);
+	recptr = XLogInsert(RM_MULTIXACT_ID, XLOG_MULTIXACT_TRUNCATE_ID);
+	XLogFlush(recptr);
+}
+
+/*
  * MULTIXACT resource manager's routines
  */
 void
@@ -3255,6 +3330,49 @@ multixact_redo(XLogReaderState *record)
 			LWLockRelease(XidGenLock);
 		}
 	}
+	else if (info == XLOG_MULTIXACT_TRUNCATE_ID)
+	{
+		xl_multixact_truncate xlrec;
+		int			pageno;
+
+		memcpy(&xlrec, XLogRecGetData(record),
+			   SizeOfMultiXactTruncate);
+
+		elog(DEBUG1, "replaying multixact truncation: "
+			 "offsets [%u, %u), offsets segments [%x, %x), "
+			 "members [%u, %u), members segments [%x, %x)",
+			 xlrec.startTruncOff, xlrec.endTruncOff,
+			 MultiXactIdToOffsetSegment(xlrec.startTruncOff),
+			 MultiXactIdToOffsetSegment(xlrec.endTruncOff),
+			 xlrec.startTruncMemb, xlrec.endTruncMemb,
+			 MXOffsetToMemberSegment(xlrec.startTruncMemb),
+			 MXOffsetToMemberSegment(xlrec.endTruncMemb));
+
+		/* should not be required, but more than cheap enough */
+		LWLockAcquire(MultiXactTruncationLock, LW_EXCLUSIVE);
+
+		/*
+		 * Advance the horizon values, so they're current at the end of
+		 * recovery.
+		 */
+		SetMultiXactIdLimit(xlrec.endTruncOff, xlrec.oldestMultiDB);
+
+		PerformMembersTruncation(xlrec.startTruncMemb, xlrec.endTruncMemb);
+
+		/*
+		 * During XLOG replay, latest_page_number isn't necessarily set up
+		 * yet; insert a suitable value to bypass the sanity test in
+		 * SimpleLruTruncate.
+		 */
+		pageno = MultiXactIdToOffsetPage(xlrec.endTruncOff);
+		MultiXactOffsetCtl->shared->latest_page_number = pageno;
+		PerformOffsetsTruncation(xlrec.startTruncOff, xlrec.endTruncOff);
+
+		LWLockRelease(MultiXactTruncationLock);
+
+		/* only looked at in the startup process, no lock necessary */
+		MultiXactState->sawTruncationInCkptCycle = true;
+	}
 	else
 		elog(PANIC, "multixact_redo: unknown op code %u", info);
 }
diff --git a/src/backend/access/transam/slru.c b/src/backend/access/transam/slru.c
index 5fcea11..90c7cf5 100644
--- a/src/backend/access/transam/slru.c
+++ b/src/backend/access/transam/slru.c
@@ -134,6 +134,7 @@ static int	SlruSelectLRUPage(SlruCtl ctl, int pageno);
 
 static bool SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename,
 						  int segpage, void *data);
+static void SlruInternalDeleteSegment(SlruCtl ctl, char *filename);
 
 /*
  * Initialization of shared memory
@@ -1075,7 +1076,7 @@ SlruSelectLRUPage(SlruCtl ctl, int pageno)
  * Flush dirty pages to disk during checkpoint or database shutdown
  */
 void
-SimpleLruFlush(SlruCtl ctl, bool checkpoint)
+SimpleLruFlush(SlruCtl ctl, bool allow_redirtied)
 {
 	SlruShared	shared = ctl->shared;
 	SlruFlushData fdata;
@@ -1096,11 +1097,11 @@ SimpleLruFlush(SlruCtl ctl, bool checkpoint)
 		SlruInternalWritePage(ctl, slotno, &fdata);
 
 		/*
-		 * When called during a checkpoint, we cannot assert that the slot is
-		 * clean now, since another process might have re-dirtied it already.
-		 * That's okay.
+		 * In some places (e.g. checkpoints), we cannot assert that the slot
+		 * is clean now, since another process might have re-dirtied it
+		 * already.  That's okay.
 		 */
-		Assert(checkpoint ||
+		Assert(allow_redirtied ||
 			   shared->page_status[slotno] == SLRU_PAGE_EMPTY ||
 			   (shared->page_status[slotno] == SLRU_PAGE_VALID &&
 				!shared->page_dirty[slotno]));
@@ -1210,8 +1211,14 @@ restart:;
 	(void) SlruScanDirectory(ctl, SlruScanDirCbDeleteCutoff, &cutoffPage);
 }
 
-void
-SlruDeleteSegment(SlruCtl ctl, char *filename)
+/*
+ * Delete an individual SLRU segment, identified by the filename.
+ *
+ * NB: This does not touch the SLRU buffers themselves, callers have to ensure
+ * they either can't yet contain anything, or have already been cleaned out.
+ */
+static void
+SlruInternalDeleteSegment(SlruCtl ctl, char *filename)
 {
 	char		path[MAXPGPATH];
 
@@ -1222,6 +1229,64 @@ SlruDeleteSegment(SlruCtl ctl, char *filename)
 }
 
 /*
+ * Delete an individual SLRU segment, identified by the segment number.
+ */
+void
+SlruDeleteSegment(SlruCtl ctl, int segno)
+{
+	SlruShared	shared = ctl->shared;
+	int			slotno;
+	char		path[MAXPGPATH];
+	bool		did_write;
+
+	/* Clean out any possibly existing references to the segment. */
+	LWLockAcquire(shared->ControlLock, LW_EXCLUSIVE);
+restart:
+	did_write = false;
+	for (slotno = 0; slotno < shared->num_slots; slotno++)
+	{
+		int			pagesegno = shared->page_number[slotno] / SLRU_PAGES_PER_SEGMENT;
+
+		if (shared->page_status[slotno] == SLRU_PAGE_EMPTY)
+			continue;
+
+		/* not the segment we're looking for */
+		if (pagesegno != segno)
+			continue;
+
+		/* If page is clean, just change state to EMPTY (expected case). */
+		if (shared->page_status[slotno] == SLRU_PAGE_VALID &&
+			!shared->page_dirty[slotno])
+		{
+			shared->page_status[slotno] = SLRU_PAGE_EMPTY;
+			continue;
+		}
+
+		/* Same logic as SimpleLruTruncate() */
+		if (shared->page_status[slotno] == SLRU_PAGE_VALID)
+			SlruInternalWritePage(ctl, slotno, NULL);
+		else
+			SimpleLruWaitIO(ctl, slotno);
+
+		did_write = true;
+	}
+
+	/*
+	 * Be extra careful and re-check. The IO functions release the control
+	 * lock, so new pages could have been read in.
+	 */
+	if (did_write)
+		goto restart;
+
+	snprintf(path, MAXPGPATH, "%s/%04X", ctl->Dir, segno);
+	ereport(DEBUG2,
+			(errmsg("removing file \"%s\"", path)));
+	unlink(path);
+
+	LWLockRelease(shared->ControlLock);
+}
+
+/*
  * SlruScanDirectory callback
  *		This callback reports true if there's any segment prior to the one
  *		containing the page passed as "data".
@@ -1249,7 +1314,7 @@ SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename, int segpage, void *data)
 	int			cutoffPage = *(int *) data;
 
 	if (ctl->PagePrecedes(segpage, cutoffPage))
-		SlruDeleteSegment(ctl, filename);
+		SlruInternalDeleteSegment(ctl, filename);
 
 	return false;				/* keep going */
 }
@@ -1261,7 +1326,7 @@ SlruScanDirCbDeleteCutoff(SlruCtl ctl, char *filename, int segpage, void *data)
 bool
 SlruScanDirCbDeleteAll(SlruCtl ctl, char *filename, int segpage, void *data)
 {
-	SlruDeleteSegment(ctl, filename);
+	SlruInternalDeleteSegment(ctl, filename);
 
 	return false;				/* keep going */
 }
diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index a87f09e..1ac1c05 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -6330,7 +6330,6 @@ StartupXLOG(void)
 	SetMultiXactIdLimit(checkPoint.oldestMulti, checkPoint.oldestMultiDB);
 	SetCommitTsLimit(checkPoint.oldestCommitTs,
 					 checkPoint.newestCommitTs);
-	MultiXactSetSafeTruncate(checkPoint.oldestMulti);
 	XLogCtl->ckptXidEpoch = checkPoint.nextXidEpoch;
 	XLogCtl->ckptXid = checkPoint.nextXid;
 
@@ -6347,10 +6346,8 @@ StartupXLOG(void)
 	StartupReorderBuffer();
 
 	/*
-	 * Startup MultiXact.  We need to do this early for two reasons: one is
-	 * that we might try to access multixacts when we do tuple freezing, and
-	 * the other is we need its state initialized because we attempt
-	 * truncation during restartpoints.
+	 * Startup MultiXact. We need to do this early to be able to replay
+	 * truncations.
 	 */
 	StartupMultiXact();
 
@@ -8508,12 +8505,6 @@ CreateCheckPoint(int flags)
 	END_CRIT_SECTION();
 
 	/*
-	 * Now that the checkpoint is safely on disk, we can update the point to
-	 * which multixact can be truncated.
-	 */
-	MultiXactSetSafeTruncate(checkPoint.oldestMulti);
-
-	/*
 	 * Let smgr do post-checkpoint cleanup (eg, deleting old files).
 	 */
 	smgrpostckpt();
@@ -8552,11 +8543,6 @@ CreateCheckPoint(int flags)
 	if (!RecoveryInProgress())
 		TruncateSUBTRANS(GetOldestXmin(NULL, false));
 
-	/*
-	 * Truncate pg_multixact too.
-	 */
-	TruncateMultiXact();
-
 	/* Real work is done, but log and update stats before releasing lock. */
 	LogCheckpointEnd(false);
 
@@ -8887,21 +8873,6 @@ CreateRestartPoint(int flags)
 	}
 
 	/*
-	 * Due to a historical accident multixact truncations are not WAL-logged,
-	 * but just performed everytime the mxact horizon is increased. So, unless
-	 * we explicitly execute truncations on a standby it will never clean out
-	 * /pg_multixact which obviously is bad, both because it uses space and
-	 * because we can wrap around into pre-existing data...
-	 *
-	 * We can only do the truncation here, after the UpdateControlFile()
-	 * above, because we've now safely established a restart point.  That
-	 * guarantees we will not need to access those multis.
-	 *
-	 * It's probably worth improving this.
-	 */
-	TruncateMultiXact();
-
-	/*
 	 * Truncate pg_subtrans if possible.  We can throw away all data before
 	 * the oldest XMIN of any running transaction.  No future transaction will
 	 * attempt to reference any pg_subtrans entry older than that (see Asserts
@@ -9261,9 +9232,14 @@ xlog_redo(XLogReaderState *record)
 		LWLockRelease(OidGenLock);
 		MultiXactSetNextMXact(checkPoint.nextMulti,
 							  checkPoint.nextMultiOffset);
+
+		/*
+		 * NB: This may perform multixact truncation when replaying WAL
+		 * generated by an older primary.
+		 */
+		MultiXactAdvanceOldest(checkPoint.oldestMulti,
+							   checkPoint.oldestMultiDB);
 		SetTransactionIdLimit(checkPoint.oldestXid, checkPoint.oldestXidDB);
-		SetMultiXactIdLimit(checkPoint.oldestMulti, checkPoint.oldestMultiDB);
-		MultiXactSetSafeTruncate(checkPoint.oldestMulti);
 
 		/*
 		 * If we see a shutdown checkpoint while waiting for an end-of-backup
@@ -9353,14 +9329,17 @@ xlog_redo(XLogReaderState *record)
 		LWLockRelease(OidGenLock);
 		MultiXactAdvanceNextMXact(checkPoint.nextMulti,
 								  checkPoint.nextMultiOffset);
+
+		/*
+		 * NB: This may perform multixact truncation when replaying WAL
+		 * generated by an older primary.
+		 */
+		MultiXactAdvanceOldest(checkPoint.oldestMulti,
+							   checkPoint.oldestMultiDB);
 		if (TransactionIdPrecedes(ShmemVariableCache->oldestXid,
 								  checkPoint.oldestXid))
 			SetTransactionIdLimit(checkPoint.oldestXid,
 								  checkPoint.oldestXidDB);
-		MultiXactAdvanceOldest(checkPoint.oldestMulti,
-							   checkPoint.oldestMultiDB);
-		MultiXactSetSafeTruncate(checkPoint.oldestMulti);
-
 		/* ControlFile->checkPointCopy always tracks the latest ckpt XID */
 		ControlFile->checkPointCopy.nextXidEpoch = checkPoint.nextXidEpoch;
 		ControlFile->checkPointCopy.nextXid = checkPoint.nextXid;
diff --git a/src/backend/commands/vacuum.c b/src/backend/commands/vacuum.c
index 85b0483..698bb35 100644
--- a/src/backend/commands/vacuum.c
+++ b/src/backend/commands/vacuum.c
@@ -1137,11 +1137,11 @@ vac_truncate_clog(TransactionId frozenXID,
 		return;
 
 	/*
-	 * Truncate CLOG and CommitTs to the oldest computed value. Note we don't
-	 * truncate multixacts; that will be done by the next checkpoint.
+	 * Truncate CLOG, multixact and CommitTs to the oldest computed value.
 	 */
 	TruncateCLOG(frozenXID);
 	TruncateCommitTs(frozenXID, true);
+	TruncateMultiXact(minMulti, minmulti_datoid, false);
 
 	/*
 	 * Update the wrap limit for GetNewTransactionId and creation of new
diff --git a/src/backend/storage/lmgr/lwlocknames.txt b/src/backend/storage/lmgr/lwlocknames.txt
index 96bbfe8..c557cb6 100644
--- a/src/backend/storage/lmgr/lwlocknames.txt
+++ b/src/backend/storage/lmgr/lwlocknames.txt
@@ -45,3 +45,4 @@ ReplicationSlotControlLock			37
 CommitTsControlLock					38
 CommitTsLock						39
 ReplicationOriginLock				40
+MultiXactTruncationLock				41
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index 6213f8a..47ef38d 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -71,6 +71,7 @@ typedef struct MultiXactMember
 #define XLOG_MULTIXACT_ZERO_OFF_PAGE	0x00
 #define XLOG_MULTIXACT_ZERO_MEM_PAGE	0x10
 #define XLOG_MULTIXACT_CREATE_ID		0x20
+#define XLOG_MULTIXACT_TRUNCATE_ID		0x30
 
 typedef struct xl_multixact_create
 {
@@ -82,6 +83,21 @@ typedef struct xl_multixact_create
 
 #define SizeOfMultiXactCreate (offsetof(xl_multixact_create, members))
 
+typedef struct xl_multixact_truncate
+{
+	Oid			oldestMultiDB;
+
+	/* to-be-truncated range of multixact offsets */
+	MultiXactId startTruncOff;	/* just for completeness' sake */
+	MultiXactId endTruncOff;
+
+	/* to-be-truncated range of multixact members */
+	MultiXactOffset startTruncMemb;
+	MultiXactOffset endTruncMemb;
+} xl_multixact_truncate;
+
+#define SizeOfMultiXactTruncate (sizeof(xl_multixact_truncate))
+
 
 extern MultiXactId MultiXactIdCreate(TransactionId xid1,
 				  MultiXactStatus status1, TransactionId xid2,
@@ -120,13 +136,12 @@ extern void MultiXactGetCheckptMulti(bool is_shutdown,
 						 Oid *oldestMultiDB);
 extern void CheckPointMultiXact(void);
 extern MultiXactId GetOldestMultiXactId(void);
-extern void TruncateMultiXact(void);
+extern void TruncateMultiXact(MultiXactId oldestMulti, Oid oldestMultiDB, bool in_recovery);
 extern void MultiXactSetNextMXact(MultiXactId nextMulti,
 					  MultiXactOffset nextMultiOffset);
 extern void MultiXactAdvanceNextMXact(MultiXactId minMulti,
 						  MultiXactOffset minMultiOffset);
 extern void MultiXactAdvanceOldest(MultiXactId oldestMulti, Oid oldestMultiDB);
-extern void MultiXactSetSafeTruncate(MultiXactId safeTruncateMulti);
 extern int	MultiXactMemberFreezeThreshold(void);
 
 extern void multixact_twophase_recover(TransactionId xid, uint16 info,
diff --git a/src/include/access/slru.h b/src/include/access/slru.h
index 9c7f019..f60e75b 100644
--- a/src/include/access/slru.h
+++ b/src/include/access/slru.h
@@ -143,14 +143,14 @@ extern int SimpleLruReadPage(SlruCtl ctl, int pageno, bool write_ok,
 extern int SimpleLruReadPage_ReadOnly(SlruCtl ctl, int pageno,
 						   TransactionId xid);
 extern void SimpleLruWritePage(SlruCtl ctl, int slotno);
-extern void SimpleLruFlush(SlruCtl ctl, bool checkpoint);
+extern void SimpleLruFlush(SlruCtl ctl, bool allow_redirtied);
 extern void SimpleLruTruncate(SlruCtl ctl, int cutoffPage);
 extern bool SimpleLruDoesPhysicalPageExist(SlruCtl ctl, int pageno);
 
 typedef bool (*SlruScanCallback) (SlruCtl ctl, char *filename, int segpage,
 											  void *data);
 extern bool SlruScanDirectory(SlruCtl ctl, SlruScanCallback callback, void *data);
-extern void SlruDeleteSegment(SlruCtl ctl, char *filename);
+extern void SlruDeleteSegment(SlruCtl ctl, int segno);
 
 /* SlruScanDirectory public callbacks */
 extern bool SlruScanDirCbReportPresence(SlruCtl ctl, char *filename,
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index a037f81..0e149ea 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2750,6 +2750,7 @@ xl_invalid_page
 xl_invalid_page_key
 xl_multi_insert_tuple
 xl_multixact_create
+xl_multixact_truncate
 xl_parameter_change
 xl_relmap_update
 xl_replorigin_drop
-- 
2.5.0.400.gff86faf

diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index cb12fc3..cb4a0cd 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -2945,29 +2945,6 @@ SlruScanDirCbRemoveMembers(SlruCtl ctl, char *filename, int segpage,
 	return false;				/* keep going */
 }
 
-typedef struct mxtruncinfo
-{
-	int			earliestExistingPage;
-} mxtruncinfo;
-
-/*
- * SlruScanDirectory callback
- *		This callback determines the earliest existing page number.
- */
-static bool
-SlruScanDirCbFindEarliest(SlruCtl ctl, char *filename, int segpage, void *data)
-{
-	mxtruncinfo *trunc = (mxtruncinfo *) data;
-
-	if (trunc->earliestExistingPage == -1 ||
-		ctl->PagePrecedes(segpage, trunc->earliestExistingPage))
-	{
-		trunc->earliestExistingPage = segpage;
-	}
-
-	return false;				/* keep going */
-}
-
 /*
  * Remove all MultiXactOffset and MultiXactMember segments before the oldest
  * ones still of interest.
@@ -2986,8 +2963,6 @@ TruncateMultiXact(void)
 	MultiXactOffset oldestOffset;
 	MultiXactId		nextMXact;
 	MultiXactOffset	nextOffset;
-	mxtruncinfo trunc;
-	MultiXactId earliest;
 	MembersLiveRange range;
 
 	Assert(AmCheckpointerProcess() || AmStartupProcess() ||
@@ -3001,49 +2976,20 @@ TruncateMultiXact(void)
 	Assert(MultiXactIdIsValid(oldestMXact));
 
 	/*
-	 * Note we can't just plow ahead with the truncation; it's possible that
-	 * there are no segments to truncate, which is a problem because we are
-	 * going to attempt to read the offsets page to determine where to
-	 * truncate the members SLRU.  So we first scan the directory to determine
-	 * the earliest offsets page number that we can read without error.
-	 */
-	trunc.earliestExistingPage = -1;
-	SlruScanDirectory(MultiXactOffsetCtl, SlruScanDirCbFindEarliest, &trunc);
-	earliest = trunc.earliestExistingPage * MULTIXACT_OFFSETS_PER_PAGE;
-	if (earliest < FirstMultiXactId)
-		earliest = FirstMultiXactId;
-
-	/*
-	 * If there's nothing to remove, we can bail out early.
-	 *
-	 * Due to bugs in early releases of PostgreSQL 9.3.X and 9.4.X,
-	 * oldestMXact might point to a multixact that does not exist.
-	 * Autovacuum will eventually advance it to a value that does exist,
-	 * and we want to set a proper offsetStopLimit when that happens,
-	 * so call DetermineSafeOldestOffset here even if we're not actually
-	 * truncating.
-	 */
-	if (MultiXactIdPrecedes(oldestMXact, earliest))
-	{
-		DetermineSafeOldestOffset(oldestMXact);
-		return;
-	}
-
-	/*
 	 * First, compute the safe truncation point for MultiXactMember. This is
 	 * the starting offset of the oldest multixact.
 	 *
-	 * Hopefully, find_multixact_start will always work here, because we've
-	 * already checked that it doesn't precede the earliest MultiXact on
-	 * disk.  But if it fails, don't truncate anything, and log a message.
+	 * Due to bugs in early releases of PostgreSQL 9.3.X and 9.4.X,
+	 * oldestMXact might point to a multixact that does not exist.  Call
+	 * DetermineSafeOldestOffset() to emit the message about disabled member
+	 * wraparound protection.  Autovacuum will eventually advance oldestMXact
+	 * to a value that does exist.
 	 */
 	if (oldestMXact == nextMXact)
 		oldestOffset = nextOffset;		/* there are NO MultiXacts */
 	else if (!find_multixact_start(oldestMXact, &oldestOffset))
 	{
-		ereport(LOG,
-				(errmsg("oldest MultiXact %u not found, earliest MultiXact %u, skipping truncation",
-					oldestMXact, earliest)));
+		DetermineSafeOldestOffset(oldestMXact);
 		return;
 	}
 

>From d26d41a96a7fc8dbe9827d55837875790b21ca1b Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Sat, 12 Dec 2015 17:57:21 +0100
Subject: [PATCH 1/2] Fix bug in SetOffsetVacuumLimit() triggered by
 find_multixact_start() failure.

In case find_multixact_start() failed SetOffsetVacuumLimit() installed 0
into MultiXactState->offsetStopLimit. Unlike oldestOffset the
to-be-installed value was not restored in the error branch.

Luckily there are no known cases where find_multixact_start() will
return an error in 9.5 and above.

But if the bug is triggered, e.g. due to filesystem permission issues,
it'd be somewhat bad: GetNewMultiXactId() could continue allocating
mxids even if close to a wraparound, or it could erroneously stop
allocating mxids, even if no wraparound is looming.  Luckily the wrong
value would be corrected the next time SetOffsetVacuumLimit() is called,
or by a restart.

Reported-By: Noah Misch, although this is not his preferred fix
Backpatch: 9.5, where the bug was introduced as part of 4f627f
---
 src/backend/access/transam/multixact.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index b66a2b6..d2619bd 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -2552,6 +2552,7 @@ SetOffsetVacuumLimit(void)
 	bool		oldestOffsetKnown = false;
 	bool		prevOldestOffsetKnown;
 	MultiXactOffset offsetStopLimit = 0;
+	MultiXactOffset prevOffsetStopLimit;
 
 	/*
 	 * NB: Have to prevent concurrent truncation, we might otherwise try to
@@ -2566,6 +2567,7 @@ SetOffsetVacuumLimit(void)
 	nextOffset = MultiXactState->nextOffset;
 	prevOldestOffsetKnown = MultiXactState->oldestOffsetKnown;
 	prevOldestOffset = MultiXactState->oldestOffset;
+	prevOffsetStopLimit = MultiXactState->offsetStopLimit;
 	Assert(MultiXactState->finishedStartup);
 	LWLockRelease(MultiXactGenLock);
 
@@ -2633,11 +2635,13 @@ SetOffsetVacuumLimit(void)
 	{
 		/*
 		 * If we failed to get the oldest offset this time, but we have a
-		 * value from a previous pass through this function, use the old value
-		 * rather than automatically forcing it.
+		 * value from a previous pass through this function, use the old
+		 * values rather than automatically forcing an emergency autovacuum
+		 * cycle again.
 		 */
 		oldestOffset = prevOldestOffset;
 		oldestOffsetKnown = true;
+		offsetStopLimit = prevOffsetStopLimit;
 	}
 
 	/* Install the computed values */
-- 
2.6.0.rc3

>From addafc27e7b89187a3f55a2cbce136d58722c97b Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Sat, 12 Dec 2015 17:53:41 +0100
Subject: [PATCH 2/2] Improve/Fix comments around multixact truncation.

My commits 4f627f8 ("Rework the way multixact truncations work.") and
aa29c1c ("Remove legacy multixact truncation support.") missed updating
a number of comments. Fix that. Additionally improve accuracy of a few
of the added comments.

Reported-By: Noah Misch
Author: Slightly edited subset of a larger patchset by Noah Misch
Backpatch: 9.5, which is the first branch to contain the above commits
---
 src/backend/access/heap/README.tuplock |  6 ++----
 src/backend/access/transam/multixact.c | 36 +++++++++++++++++++---------------
 src/backend/access/transam/xlog.c      |  4 ----
 3 files changed, 22 insertions(+), 24 deletions(-)

diff --git a/src/backend/access/heap/README.tuplock b/src/backend/access/heap/README.tuplock
index 10b8d78..f845958 100644
--- a/src/backend/access/heap/README.tuplock
+++ b/src/backend/access/heap/README.tuplock
@@ -102,10 +102,8 @@ the MultiXacts in them are no longer of interest.
 VACUUM is in charge of removing old MultiXacts at the time of tuple freezing.
 The lower bound used by vacuum (that is, the value below which all multixacts
 are removed) is stored as pg_class.relminmxid for each table; the minimum of
-all such values is stored in pg_database.datminmxid.  The minimum across
-all databases, in turn, is recorded in checkpoint records, and CHECKPOINT
-removes pg_multixact/ segments older than that value once the checkpoint
-record has been flushed.
+all such values is stored in pg_database.datminmxid.  VACUUM removes
+pg_multixact/ segments older than the minimum datminmxid across databases.
 
 Infomask Bits
 -------------
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index d2619bd..fdeb90b 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -257,7 +257,7 @@ typedef struct MultiXactStateData
 	 * we compute it (using nextMXact if none are valid).  Each backend is
 	 * required not to attempt to access any SLRU data for MultiXactIds older
 	 * than its own OldestVisibleMXactId[] setting; this is necessary because
-	 * the checkpointer could truncate away such data at any instant.
+	 * VACUUM could truncate away such data at any instant.
 	 *
 	 * The oldest valid value among all of the OldestMemberMXactId[] and
 	 * OldestVisibleMXactId[] entries is considered by vacuum as the earliest
@@ -271,8 +271,8 @@ typedef struct MultiXactStateData
 	 * the freezing point so computed is used as the new pg_class.relminmxid
 	 * value.  The minimum of all those values in a database is stored as
 	 * pg_database.datminmxid.  In turn, the minimum of all of those values is
-	 * stored in pg_control and used as truncation point for pg_multixact.  At
-	 * checkpoint or restartpoint, unneeded segments are removed.
+	 * stored in pg_control and used as truncation point for pg_multixact.
+	 * VACUUM removes unneeded segments.
 	 */
 	MultiXactId perBackendXactIds[FLEXIBLE_ARRAY_MEMBER];
 } MultiXactStateData;
@@ -662,8 +662,8 @@ MultiXactIdSetOldestMember(void)
  *
  * We set the OldestVisibleMXactId for a given transaction the first time
  * it's going to inspect any MultiXactId.  Once we have set this, we are
- * guaranteed that the checkpointer won't truncate off SLRU data for
- * MultiXactIds at or after our OldestVisibleMXactId.
+ * guaranteed that VACUUM won't truncate off SLRU data for MultiXactIds at
+ * or after our OldestVisibleMXactId.
  *
  * The value to set is the oldest of nextMXact and all the valid per-backend
  * OldestMemberMXactId[] entries.  Because of the locking we do, we can be
@@ -2207,9 +2207,7 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 	/*
 	 * We pretend that a wrap will happen halfway through the multixact ID
 	 * space, but that's not really true, because multixacts wrap differently
-	 * from transaction IDs.  Note that, separately from any concern about
-	 * multixact IDs wrapping, we must ensure that multixact members do not
-	 * wrap.  Limits for that are set in DetermineSafeOldestOffset, not here.
+	 * from transaction IDs.
 	 */
 	multiWrapLimit = oldest_datminmxid + (MaxMultiXactId >> 1);
 	if (multiWrapLimit < FirstMultiXactId)
@@ -2253,7 +2251,7 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 	if (multiVacLimit < FirstMultiXactId)
 		multiVacLimit += FirstMultiXactId;
 
-	/* Grab lock for just long enough to set the new limit values */
+	/* Grab lock for just long enough to set the new MultiXactId bounds */
 	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
 	MultiXactState->oldestMultiXactId = oldest_datminmxid;
 	MultiXactState->oldestMultiXactDB = oldest_datoid;
@@ -2270,11 +2268,11 @@ SetMultiXactIdLimit(MultiXactId oldest_datminmxid, Oid oldest_datoid)
 			 multiWrapLimit, oldest_datoid)));
 
 	/*
-	 * Computing the actual limits is only possible once the data directory is
-	 * in a consistent state. There's no need to compute the limits while
-	 * still replaying WAL - no decisions about new multis are made even
-	 * though multixact creations might be replayed. So we'll only do further
-	 * checks after TrimMultiXact() has been called.
+	 * Setting MultiXactState->oldestOffset (in SetOffsetVacuumLimit())
+	 * entails a find_multixact_start() call, which is only possible once the
+	 * data directory is in a consistent state. There's no need for an offset
+	 * limit while still replaying WAL; no decisions about new multis are made
+	 * even though multixact creations might be replayed.
 	 */
 	if (!MultiXactState->finishedStartup)
 		return;
@@ -3069,8 +3067,8 @@ TruncateMultiXact(MultiXactId newOldestMulti, Oid newOldestMultiDB)
 	 * the critical section: Have to do it before truncation, to prevent
 	 * concurrent lookups of those values. Has to be inside the critical
 	 * section as otherwise a future call to this function would error out,
-	 * while looking up the oldest member in offsets, if our caller crashes
-	 * before updating the limits.
+	 * while looking up the oldest member in offsets, given ereport(ERROR)
+	 * before our caller updates the limits.
 	 */
 	LWLockAcquire(MultiXactGenLock, LW_EXCLUSIVE);
 	MultiXactState->oldestMultiXactId = newOldestMulti;
@@ -3185,6 +3183,12 @@ WriteMZeroPageXlogRec(int pageno, uint8 info)
 /*
  * Write a TRUNCATE xlog record
  *
+ * Flushing the record to disk serves two critical roles.  Like it is with
+ * TruncateCLOG(), recent HEAP_FREEZE records must reach disk before we delete
+ * any MultiXactId they overwrote.  This flush before unlinking any segment
+ * ensures that a crash/basebackup and recovery will not make
+ * MultiXactState->oldestMultiXactId point to a missing segment.
+
  * We must flush the xlog record to disk before returning --- see notes in
  * TruncateCLOG().
  */
diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index 71fc8ff..35d76de 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -9319,10 +9319,6 @@ xlog_redo(XLogReaderState *record)
 		MultiXactAdvanceNextMXact(checkPoint.nextMulti,
 								  checkPoint.nextMultiOffset);
 
-		/*
-		 * NB: This may perform multixact truncation when replaying WAL
-		 * generated by an older primary.
-		 */
 		MultiXactAdvanceOldest(checkPoint.oldestMulti,
 							   checkPoint.oldestMultiDB);
 		if (TransactionIdPrecedes(ShmemVariableCache->oldestXid,
-- 
2.6.0.rc3