pgsql: Fix a couple of bugs in MultiXactId freezing

*** a/src/backend/access/heap/heapam.c
--- b/src/backend/access/heap/heapam.c
***************
*** 5384,5412 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  			TransactionId	update_xid;
  
  			/*
! 			 * This is a multixact which is not marked LOCK_ONLY, but which
! 			 * is newer than the cutoff_multi.  If the update_xid is below the
! 			 * cutoff_xid point, then we can just freeze the Xmax in the
! 			 * tuple, removing it altogether.  This seems simple, but there
! 			 * are several underlying assumptions:
! 			 *
! 			 * 1. A tuple marked by an multixact containing a very old
! 			 * committed update Xid would have been pruned away by vacuum; we
! 			 * wouldn't be freezing this tuple at all.
! 			 *
! 			 * 2. There cannot possibly be any live locking members remaining
! 			 * in the multixact.  This is because if they were alive, the
! 			 * update's Xid would had been considered, via the lockers'
! 			 * snapshot's Xmin, as part the cutoff_xid.
! 			 *
! 			 * 3. We don't create new MultiXacts via MultiXactIdExpand() that
! 			 * include a very old aborted update Xid: in that function we only
! 			 * include update Xids corresponding to transactions that are
! 			 * committed or in-progress.
  			 */
  			update_xid = HeapTupleGetUpdateXid(tuple);
  			if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 				freeze_xmax = true;
  		}
  	}
  	else if (TransactionIdIsNormal(xid) &&
--- 5384,5404 ----
  			TransactionId	update_xid;
  
  			/*
! 			 * This is a multixact which is not marked LOCK_ONLY, but which is
! 			 * newer than the cutoff_multi.  To advance relfrozenxid, we must
! 			 * eliminate any updater XID that falls below cutoff_xid.
! 			 * Affected multixacts may also contain outstanding lockers, which
! 			 * we must preserve.  Forming a new multixact is tempting, but
! 			 * solving it that way requires a WAL format change.  Instead,
! 			 * mark the tuple LOCK_ONLY.  The updater XID is still present,
! 			 * but consuming code will notice LOCK_ONLY and assume it's gone.
  			 */
  			update_xid = HeapTupleGetUpdateXid(tuple);
  			if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 			{
! 				tuple->t_infomask |= HEAP_XMAX_LOCK_ONLY;
! 				changed = true;
! 			}
  		}
  	}
  	else if (TransactionIdIsNormal(xid) &&

commit 4be26fe1ebc3b198d093a0334e033bb70516fa60
Author: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date:   Tue Dec 3 15:06:40 2013 -0300

    Fixup "Don't TransactionIdDidAbort in ..." patch
    
    Noah Misch reported a failure in the new freezing logic for MultiXactIds,
    providing a test case that demonstrated it; further investigation revealed a
    problem that HeapTupleSatisfiesUpdate routine could ignore in-progress locker
    transactions for a tuple whose Xmax is a MultiXactId that contains an aborted
    update.  In short, the lock would suddenly go ignored by other transactions.
    
    This change reverts the change to the delete-abort-savept isolation test;
    turns out changing it was in error.
    
    Andres Freund and Álvaro Herrera

diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index 4d63b1c..f787f2c 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -789,13 +789,26 @@ HeapTupleSatisfiesUpdate(HeapTupleHeader tuple, CommandId curcid,
 		if (TransactionIdDidCommit(xmax))
 			return HeapTupleUpdated;
 
-		/* no member, even just a locker, alive anymore */
+		/*
+		 * By here, the update in the Xmax is either aborted or crashed, but
+		 * what about the other members?
+		 */
+
 		if (!MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
+		{
+			/*
+			 * There's no member, even just a locker, alive anymore, so we can
+			 * mark the Xmax as invalid.
+			 */
 			SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 						InvalidTransactionId);
-
-		/* it must have aborted or crashed */
-		return HeapTupleMayBeUpdated;
+			return HeapTupleMayBeUpdated;
+		}
+		else
+		{
+			/* There are lockers running */
+			return HeapTupleBeingUpdated;
+		}
 	}
 
 	if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
diff --git a/src/test/isolation/expected/delete-abort-savept.out b/src/test/isolation/expected/delete-abort-savept.out
index 5b8c444..3420cf4 100644
--- a/src/test/isolation/expected/delete-abort-savept.out
+++ b/src/test/isolation/expected/delete-abort-savept.out
@@ -23,11 +23,12 @@ key            value
 step s1svp: SAVEPOINT f;
 step s1d: DELETE FROM foo;
 step s1r: ROLLBACK TO f;
-step s2l: SELECT * FROM foo FOR UPDATE;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1c: COMMIT;
+step s2l: <... completed>
 key            value          
 
 1              1              
-step s1c: COMMIT;
 step s2c: COMMIT;
 
 starting permutation: s1l s1svp s1d s1r s2l s2c s1c
@@ -38,12 +39,8 @@ key            value
 step s1svp: SAVEPOINT f;
 step s1d: DELETE FROM foo;
 step s1r: ROLLBACK TO f;
-step s2l: SELECT * FROM foo FOR UPDATE;
-key            value          
-
-1              1              
-step s2c: COMMIT;
-step s1c: COMMIT;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+invalid permutation detected
 
 starting permutation: s1l s1svp s1d s2l s1r s1c s2c
 step s1l: SELECT * FROM foo FOR KEY SHARE;

>From 330d128665fcf8633e60a42e8e4a497e2975dac0 Mon Sep 17 00:00:00 2001
From: Andres Freund <andres@anarazel.de>
Date: Wed, 4 Dec 2013 00:11:20 +0100
Subject: [PATCH] WIP: new freezing format

---
 src/backend/access/heap/heapam.c       | 476 +++++++++++++++++++++++++--------
 src/backend/access/rmgrdesc/heapdesc.c |   9 +
 src/backend/access/transam/multixact.c |   3 +-
 src/backend/commands/vacuumlazy.c      |  28 +-
 src/backend/utils/time/tqual.c         |   6 +-
 src/include/access/heapam.h            |   7 +-
 src/include/access/heapam_xlog.h       |  32 ++-
 src/include/access/multixact.h         |   1 +
 8 files changed, 443 insertions(+), 119 deletions(-)

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index c13f87c..b80fa5b 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -5242,14 +5242,17 @@ heap_inplace_update(Relation relation, HeapTuple tuple)
 		CacheInvalidateHeapTuple(relation, tuple, NULL);
 }
 
-
 /*
- * heap_freeze_tuple
+ * heap_prepare_freeze_tuple
  *
  * Check to see whether any of the XID fields of a tuple (xmin, xmax, xvac)
- * are older than the specified cutoff XID.  If so, replace them with
- * FrozenTransactionId or InvalidTransactionId as appropriate, and return
- * TRUE.  Return FALSE if nothing was changed.
+ * are older than the specified cutoff XID.  If so, return enough state to
+ * later execute and WAL log replacin them with FrozenTransactionId or
+ * InvalidTransactionId as appropriate, and return TRUE.  Return FALSE if
+ * nothing was changed.
+ *
+ * The 'off' field of the freeze state has to be set at the caller, not here,
+ * if required.
  *
  * It is assumed that the caller has checked the tuple with
  * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
@@ -5258,54 +5261,44 @@ heap_inplace_update(Relation relation, HeapTuple tuple)
  * NB: cutoff_xid *must* be <= the current global xmin, to ensure that any
  * XID older than it could neither be running nor seen as running by any
  * open transaction.  This ensures that the replacement will not change
- * anyone's idea of the tuple state.  Also, since we assume the tuple is
- * not HEAPTUPLE_DEAD, the fact that an XID is not still running allows us
- * to assume that it is either committed good or aborted, as appropriate;
- * so we need no external state checks to decide what to do.  (This is good
- * because this function is applied during WAL recovery, when we don't have
- * access to any such state, and can't depend on the hint bits to be set.)
- * There is an exception we make which is to assume GetMultiXactIdMembers can
- * be called during recovery.
- *
+ * anyone's idea of the tuple state.
  * Similarly, cutoff_multi must be less than or equal to the smallest
  * MultiXactId used by any transaction currently open.
  *
  * If the tuple is in a shared buffer, caller must hold an exclusive lock on
  * that buffer.
  *
- * Note: it might seem we could make the changes without exclusive lock, since
- * TransactionId read/write is assumed atomic anyway.  However there is a race
- * condition: someone who just fetched an old XID that we overwrite here could
- * conceivably not finish checking the XID against pg_clog before we finish
- * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
- * exclusive lock ensures no other backend is in process of checking the
- * tuple status.  Also, getting exclusive lock makes it safe to adjust the
- * infomask bits.
- *
- * NB: Cannot rely on hint bits here, they might not be set after a crash or
- * on a standby.
+ * NB: It is not enough that hint bits indicate something is committed/invalid
+ * - they might not be set on a standby/after crash recovery. So we really
+ * need to remove old xids.
  */
 bool
-heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
-				  MultiXactId cutoff_multi)
+heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+				  TransactionId cutoff_multi, xl_heap_freeze_tuple *frz)
+
 {
 	bool		changed = false;
 	bool		freeze_xmax = false;
 	TransactionId xid;
 
+	frz->freeze_xmin = false;
+	frz->invalid_xvac = false;
+	frz->freeze_xvac = false;
+	frz->t_infomask2 = tuple->t_infomask2;
+	frz->t_infomask = tuple->t_infomask;
+	frz->xmax = HeapTupleHeaderGetRawXmax(tuple);
+
 	/* Process xmin */
 	xid = HeapTupleHeaderGetXmin(tuple);
 	if (TransactionIdIsNormal(xid) &&
 		TransactionIdPrecedes(xid, cutoff_xid))
 	{
-		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
-
+		frz->freeze_xmin = true;
 		/*
 		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
 		 * already be set here, but there's a small chance not.
 		 */
-		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
-		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+		frz->t_infomask |= HEAP_XMIN_COMMITTED;
 		changed = true;
 	}
 
@@ -5332,81 +5325,139 @@ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 			/*
 			 * This old multi cannot possibly be running.  If it was a locker
 			 * only, it can be removed without much further thought; but if it
-			 * contained an update, we need to preserve it.
+			 * contained an update, we might need to preserve it.
 			 */
 			if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
+			{
 				freeze_xmax = true;
+			}
 			else
 			{
-				TransactionId update_xid;
+				/* replace multi by update xid */
+				frz->xmax = HeapTupleGetUpdateXid(tuple);
+				frz->t_infomask &= ~HEAP_XMAX_BITS;
+				frz->t_infomask &= ~HEAP_XMAX_IS_MULTI;
 
-				update_xid = HeapTupleGetUpdateXid(tuple);
+				/* wasn't only a lock, xid needs to be valid */
+				Assert(TransactionIdIsValid(frz->xmax));
 
 				/*
-				 * The multixact has an update hidden within.  Get rid of it.
-				 *
-				 * If the update_xid is below the cutoff_xid, it necessarily
-				 * must be an aborted transaction.  In a primary server, such
-				 * an Xmax would have gotten marked invalid by
-				 * HeapTupleSatisfiesVacuum, but in a replica that is not
-				 * called before we are, so deal with it in the same way.
-				 *
-				 * If not below the cutoff_xid, then the tuple would have been
-				 * pruned by vacuum, if the update committed long enough ago,
-				 * and we wouldn't be freezing it; so it's either recently
-				 * committed, or in-progress.  Deal with this by setting the
-				 * Xmax to the update Xid directly and remove the IS_MULTI
-				 * bit.  (We know there cannot be running lockers in this
-				 * multi, because it's below the cutoff_multi value.)
+				 * If the xid is older than the cutoff, it has to have
+				 * aborted, otherwise it would have gotten pruned away.
 				 */
-
-				if (TransactionIdPrecedes(update_xid, cutoff_xid))
+				if (TransactionIdPrecedes(frz->xmax, cutoff_xid))
 				{
-					Assert(InRecovery || TransactionIdDidAbort(update_xid));
+					Assert(!TransactionIdDidCommit(frz->xmax));
 					freeze_xmax = true;
 				}
 				else
 				{
-					Assert(InRecovery || !TransactionIdIsInProgress(update_xid));
-					tuple->t_infomask &= ~HEAP_XMAX_BITS;
-					HeapTupleHeaderSetXmax(tuple, update_xid);
-					changed = true;
+					/* preserve xmax */
 				}
+				changed = true;
 			}
 		}
-		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
+		else if (MultiXactIdIsRunning(xid))
 		{
-			/* newer than the cutoff, so don't touch it */
-			;
+			/* cannot be below cutoff */
 		}
 		else
 		{
-			TransactionId	update_xid;
+			TransactionId	update_xid = InvalidTransactionId;
+			MultiXactMember *members = NULL;
+			MultiXactMember *newmembers = NULL;
+			int			nmembers;
+			int			nnewmembers = 0;
+			bool		has_live_members = false;
+			bool		mxact_needs_freeze = false;
+			int			i;
 
 			/*
-			 * This is a multixact which is not marked LOCK_ONLY, but which
-			 * is newer than the cutoff_multi.  If the update_xid is below the
-			 * cutoff_xid point, then we can just freeze the Xmax in the
-			 * tuple, removing it altogether.  This seems simple, but there
-			 * are several underlying assumptions:
-			 *
-			 * 1. A tuple marked by an multixact containing a very old
-			 * committed update Xid would have been pruned away by vacuum; we
-			 * wouldn't be freezing this tuple at all.
-			 *
-			 * 2. There cannot possibly be any live locking members remaining
-			 * in the multixact.  This is because if they were alive, the
-			 * update's Xid would had been considered, via the lockers'
-			 * snapshot's Xmin, as part the cutoff_xid.
-			 *
-			 * 3. We don't create new MultiXacts via MultiXactIdExpand() that
-			 * include a very old aborted update Xid: in that function we only
-			 * include update Xids corresponding to transactions that are
-			 * committed or in-progress.
+			 * For MultiXacts that are not below the cutoff, we need to check
+			 * whether any of the members are too old.
 			 */
-			update_xid = HeapTupleGetUpdateXid(tuple);
-			if (TransactionIdPrecedes(update_xid, cutoff_xid))
+			nmembers = GetMultiXactIdMembers(xid, &members, false);
+
+			if (nmembers <= 0)
+			{
+				/* pg_upgrade'd multi, just freeze away */
+				freeze_xmax = true;
+			}
+			else
+			{
+				newmembers = (MultiXactMember *)
+					palloc(sizeof(MultiXactMember) * (nmembers + 1));
+
+				for (i = 0; i < nmembers; i++)
+				{
+					bool keep = false;
+					bool isupdate = ISUPDATE_from_mxstatus(members[i].status);
+
+					if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
+					{
+						/*
+						 * A potential updater could not have committed, tuple
+						 * would have gotten vacuumed away already.
+						 */
+						Assert(!isupdate || TransactionIdDidAbort(cutoff_xid));
+						mxact_needs_freeze = true;
+					}
+					else if (TransactionIdIsInProgress(members[i].xid))
+					{
+						keep = true;
+						if (isupdate)
+							update_xid = members[i].xid;
+					}
+					else if (TransactionIdDidCommit(members[i].xid) && isupdate)
+					{
+						/*
+						 * Only updates need to be preserved when they have
+						 * committed, locks aren't interesting anymore.
+						 */
+						keep = true;
+						update_xid = members[i].xid;
+					}
+
+					if (keep)
+					{
+						newmembers[nnewmembers++] = members[i];
+						has_live_members = true;
+					}
+				}
+			}
+
+			if (!mxact_needs_freeze)
+			{
+				/* nothing to do */;
+			}
+			else if (has_live_members &&
+					 TransactionIdIsValid(update_xid) &&
+					 nnewmembers == 1)
+			{
+				/* only the updater is still alive, replace multixact by xid */
+				frz->xmax = update_xid;
+				frz->t_infomask &= ~HEAP_XMAX_BITS;
+				frz->t_infomask |= HEAP_XMAX_COMMITTED;
+				changed = true;
+				elog(LOG, "replace multi2");
+				/* do not clear HEAP_HOT_UPDATED, HEAP_KEYS_UPDATED just yet */
+			}
+			else if (has_live_members)
+			{
+				frz->xmax = CreateMultiXactId(nnewmembers, newmembers);
+				changed = true;
+				elog(LOG, "recreating multi");
+			}
+			else
+			{
 				freeze_xmax = true;
+			}
+
+			/* cleanup memory we might have allocated */
+			if (nmembers > 0)
+				pfree(members);
+			if (newmembers != NULL)
+				pfree(newmembers);
 		}
 	}
 	else if (TransactionIdIsNormal(xid) &&
@@ -5417,20 +5468,21 @@ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 
 	if (freeze_xmax)
 	{
-		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
+		frz->xmax = InvalidTransactionId;
 
 		/*
 		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
 		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
 		 * Also get rid of the HEAP_KEYS_UPDATED bit.
 		 */
-		tuple->t_infomask &= ~HEAP_XMAX_BITS;
-		tuple->t_infomask |= HEAP_XMAX_INVALID;
-		HeapTupleHeaderClearHotUpdated(tuple);
-		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
+		frz->t_infomask &= ~HEAP_XMAX_BITS;
+		frz->t_infomask |= HEAP_XMAX_INVALID;
+		frz->t_infomask2 &= ~HEAP_HOT_UPDATED;
+		frz->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 		changed = true;
 	}
 
+
 	/*
 	 * Old-style VACUUM FULL is gone, but we have to keep this code as long as
 	 * we support having MOVED_OFF/MOVED_IN tuples in the database.
@@ -5447,16 +5499,16 @@ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 			 * xvac transaction succeeded.
 			 */
 			if (tuple->t_infomask & HEAP_MOVED_OFF)
-				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+				frz->freeze_xvac = true;
 			else
-				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+				frz->invalid_xvac = true;
 
 			/*
 			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
 			 * will already be set here, but there's a small chance not.
 			 */
 			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
-			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+			frz->t_infomask |= HEAP_XMIN_COMMITTED;
 			changed = true;
 		}
 	}
@@ -5464,6 +5516,59 @@ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 	return changed;
 }
 
+
+/*
+ * heap_freeze_tuple - freeze tuple inplace without WAL logging.
+ *
+ * Useful for callers like CLUSTER that perform their own WAL logging.
+ */
+bool
+heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+				  TransactionId cutoff_multi)
+{
+	xl_heap_freeze_tuple frz;
+	bool do_freeze;
+
+	do_freeze = heap_prepare_freeze_tuple(tuple, cutoff_xid, cutoff_multi, &frz);
+	if (do_freeze)
+		heap_execute_freeze_tuple(tuple, &frz);
+	return do_freeze;
+}
+
+/*
+ * heap_execute_freeze_tuple
+ *
+ * Execute the prepared freezing of a tuple.
+ *
+ * Note: it might seem we could make the changes without exclusive lock, since
+ * TransactionId read/write is assumed atomic anyway.  However there is a race
+ * condition: someone who just fetched an old XID that we overwrite here could
+ * conceivably not finish checking the XID against pg_clog before we finish
+ * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
+ * exclusive lock ensures no other backend is in process of checking the
+ * tuple status.  Also, getting exclusive lock makes it safe to adjust the
+ * infomask bits.
+ *
+ * NB: All code in here must be safe to execute during crash recovery!
+ */
+void
+heap_execute_freeze_tuple(HeapTupleHeader tuple, xl_heap_freeze_tuple *frz)
+{
+	if (frz->freeze_xmin)
+		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+
+	HeapTupleHeaderSetXmax(tuple, frz->xmax);
+
+	if (frz->freeze_xvac)
+		HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+
+	if (frz->invalid_xvac)
+		HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+
+	tuple->t_infomask = frz->t_infomask;
+	tuple->t_infomask2 = frz->t_infomask2;
+}
+
 /*
  * For a given MultiXactId, return the hint bits that should be set in the
  * tuple's infomask.
@@ -5767,16 +5872,26 @@ heap_tuple_needs_freeze(HeapTupleHeader tuple, TransactionId cutoff_xid,
 		}
 		else if (MultiXactIdPrecedes(multi, cutoff_multi))
 			return true;
-		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
-		{
-			/* only-locker multis don't need internal examination */
-			;
-		}
 		else
 		{
-			if (TransactionIdPrecedes(HeapTupleGetUpdateXid(tuple),
-									  cutoff_xid))
-				return true;
+			MultiXactMember *members;
+			int			nmembers;
+			int		i;
+
+			/* need to check whether any member of the mxact is too old */
+
+			nmembers = GetMultiXactIdMembers(multi, &members, false);
+
+			for (i = 0; i < nmembers; i++)
+			{
+				if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
+				{
+					pfree(members);
+					return true;
+				}
+			}
+			if (nmembers > 0)
+				pfree(members);
 		}
 	}
 	else
@@ -6031,22 +6146,22 @@ log_heap_clean(Relation reln, Buffer buffer,
  */
 XLogRecPtr
 log_heap_freeze(Relation reln, Buffer buffer,
-				TransactionId cutoff_xid, MultiXactId cutoff_multi,
-				OffsetNumber *offsets, int offcnt)
+				TransactionId cutoff_xid,
+				xl_heap_freeze_tuple *tuples, int ntuples)
 {
-	xl_heap_freeze xlrec;
+	xl_heap_freeze_page xlrec;
 	XLogRecPtr	recptr;
 	XLogRecData rdata[2];
 
 	/* Caller should not call me on a non-WAL-logged relation */
 	Assert(RelationNeedsWAL(reln));
 	/* nor when there are no tuples to freeze */
-	Assert(offcnt > 0);
+	Assert(ntuples > 0);
 
 	xlrec.node = reln->rd_node;
 	xlrec.block = BufferGetBlockNumber(buffer);
 	xlrec.cutoff_xid = cutoff_xid;
-	xlrec.cutoff_multi = cutoff_multi;
+	xlrec.ntuples = ntuples;
 
 	rdata[0].data = (char *) &xlrec;
 	rdata[0].len = SizeOfHeapFreeze;
@@ -6058,13 +6173,13 @@ log_heap_freeze(Relation reln, Buffer buffer,
 	 * it is.  When XLogInsert stores the whole buffer, the offsets array need
 	 * not be stored too.
 	 */
-	rdata[1].data = (char *) offsets;
-	rdata[1].len = offcnt * sizeof(OffsetNumber);
+	rdata[1].data = (char *) tuples;
+	rdata[1].len = ntuples * SizeOfHeapFreezeTuple;
 	rdata[1].buffer = buffer;
 	rdata[1].buffer_std = true;
 	rdata[1].next = NULL;
 
-	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE, rdata);
+	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE_PAGE, rdata);
 
 	return recptr;
 }
@@ -6406,6 +6521,99 @@ heap_xlog_clean(XLogRecPtr lsn, XLogRecord *record)
 	XLogRecordPageWithFreeSpace(xlrec->node, xlrec->block, freespace);
 }
 
+/*
+ * Freeze a single tuple for XLOG_HEAP2_FREEZE
+ *
+ * NB: This type of record aren't generated anymore, since bugs around
+ * multixacts couldn't be fixed without a more robust type of freezing. This
+ * is kept around to be able to perform PITR.
+ */
+static bool
+heap_xlog_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+				  MultiXactId cutoff_multi)
+{
+	bool		changed = false;
+	TransactionId xid;
+
+	xid = HeapTupleHeaderGetXmin(tuple);
+	if (TransactionIdIsNormal(xid) &&
+		TransactionIdPrecedes(xid, cutoff_xid))
+	{
+		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+
+		/*
+		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
+		 * already be set here, but there's a small chance not.
+		 */
+		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
+		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+		changed = true;
+	}
+
+	/*
+	 * Note that this code handles IS_MULTI Xmax values, too, but only to mark
+	 * the tuple as not updated if the multixact is below the cutoff Multixact
+	 * given; it doesn't remove dead members of a very old multixact.
+	 */
+	xid = HeapTupleHeaderGetRawXmax(tuple);
+	if ((tuple->t_infomask & HEAP_XMAX_IS_MULTI) ?
+		(MultiXactIdIsValid(xid) &&
+		 MultiXactIdPrecedes(xid, cutoff_multi)) :
+		(TransactionIdIsNormal(xid) &&
+		 TransactionIdPrecedes(xid, cutoff_xid)))
+	{
+		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
+
+		/*
+		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
+		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
+		 * Also get rid of the HEAP_KEYS_UPDATED bit.
+		 */
+		tuple->t_infomask &= ~HEAP_XMAX_BITS;
+		tuple->t_infomask |= HEAP_XMAX_INVALID;
+		HeapTupleHeaderClearHotUpdated(tuple);
+		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
+		changed = true;
+	}
+
+	/*
+	 * Old-style VACUUM FULL is gone, but we have to keep this code as long as
+	 * we support having MOVED_OFF/MOVED_IN tuples in the database.
+	 */
+	if (tuple->t_infomask & HEAP_MOVED)
+	{
+		xid = HeapTupleHeaderGetXvac(tuple);
+		if (TransactionIdIsNormal(xid) &&
+			TransactionIdPrecedes(xid, cutoff_xid))
+		{
+			/*
+			 * If a MOVED_OFF tuple is not dead, the xvac transaction must
+			 * have failed; whereas a non-dead MOVED_IN tuple must mean the
+			 * xvac transaction succeeded.
+			 */
+			if (tuple->t_infomask & HEAP_MOVED_OFF)
+				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+			else
+				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+
+			/*
+			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
+			 * will already be set here, but there's a small chance not.
+			 */
+			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
+			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+			changed = true;
+		}
+	}
+
+	return changed;
+}
+
+/*
+ * NB: This type of record aren't generated anymore, since bugs around
+ * multixacts couldn't be fixed without a more robust type of freezing. This
+ * is kept around to be able to perform PITR.
+ */
 static void
 heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
 {
@@ -6454,7 +6662,7 @@ heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
 			ItemId		lp = PageGetItemId(page, *offsets);
 			HeapTupleHeader tuple = (HeapTupleHeader) PageGetItem(page, lp);
 
-			(void) heap_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
+			(void) heap_xlog_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
 			offsets++;
 		}
 	}
@@ -6578,6 +6786,59 @@ heap_xlog_visible(XLogRecPtr lsn, XLogRecord *record)
 	}
 }
 
+/*
+ * Replay XLOG_HEAP2_FREEZE_PAGE records
+ */
+static void
+heap_xlog_freeze_page(XLogRecPtr lsn, XLogRecord *record)
+{
+	xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) XLogRecGetData(record);
+	TransactionId cutoff_xid = xlrec->cutoff_xid;
+	Buffer		buffer;
+	Page		page;
+	int			ntup;
+
+	/*
+	 * In Hot Standby mode, ensure that there's no queries running which still
+	 * consider the frozen xids as running.
+	 */
+	if (InHotStandby)
+		ResolveRecoveryConflictWithSnapshot(cutoff_xid, xlrec->node);
+
+	/* If we have a full-page image, restore it and we're done */
+	if (record->xl_info & XLR_BKP_BLOCK(0))
+	{
+		(void) RestoreBackupBlock(lsn, record, 0, false, false);
+		return;
+	}
+
+	buffer = XLogReadBuffer(xlrec->node, xlrec->block, false);
+	if (!BufferIsValid(buffer))
+		return;
+
+	page = (Page) BufferGetPage(buffer);
+
+	if (lsn <= PageGetLSN(page))
+	{
+		UnlockReleaseBuffer(buffer);
+		return;
+	}
+
+	/* now execute freeze plan for each frozen tuple */
+	for (ntup = 0; ntup < xlrec->ntuples; ntup++)
+	{
+		xl_heap_freeze_tuple *xlrec_tp = &xlrec->tuples[ntup];
+		/* offsets are one-based */
+		ItemId			lp = PageGetItemId(page, xlrec_tp->off);
+		HeapTupleHeader tuple = (HeapTupleHeader) PageGetItem(page, lp);
+		heap_execute_freeze_tuple(tuple, xlrec_tp);
+	}
+
+	PageSetLSN(page, lsn);
+	MarkBufferDirty(buffer);
+	UnlockReleaseBuffer(buffer);
+}
+
 static void
 heap_xlog_newpage(XLogRecPtr lsn, XLogRecord *record)
 {
@@ -7433,6 +7694,9 @@ heap2_redo(XLogRecPtr lsn, XLogRecord *record)
 		case XLOG_HEAP2_CLEAN:
 			heap_xlog_clean(lsn, record);
 			break;
+		case XLOG_HEAP2_FREEZE_PAGE:
+			heap_xlog_freeze_page(lsn, record);
+			break;
 		case XLOG_HEAP2_CLEANUP_INFO:
 			heap_xlog_cleanup_info(lsn, record);
 			break;
diff --git a/src/backend/access/rmgrdesc/heapdesc.c b/src/backend/access/rmgrdesc/heapdesc.c
index e14c053..1b244b1 100644
--- a/src/backend/access/rmgrdesc/heapdesc.c
+++ b/src/backend/access/rmgrdesc/heapdesc.c
@@ -149,6 +149,15 @@ heap2_desc(StringInfo buf, uint8 xl_info, char *rec)
 						 xlrec->node.relNode, xlrec->block,
 						 xlrec->latestRemovedXid);
 	}
+	if (info == XLOG_HEAP2_FREEZE_PAGE)
+	{
+		xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) rec;
+
+		appendStringInfo(buf, "freeze_page: rel %u/%u/%u; blk %u; cutoff xid %u ntuples %u",
+						 xlrec->node.spcNode, xlrec->node.dbNode,
+						 xlrec->node.relNode, xlrec->block,
+						 xlrec->cutoff_xid, xlrec->ntuples);
+	}
 	else if (info == XLOG_HEAP2_CLEANUP_INFO)
 	{
 		xl_heap_cleanup_info *xlrec = (xl_heap_cleanup_info *) rec;
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 2081470..2a1bf6f 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -286,7 +286,6 @@ static MemoryContext MXactContext = NULL;
 
 /* internal MultiXactId management */
 static void MultiXactIdSetOldestVisible(void);
-static MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members);
 static void RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
 				   int nmembers, MultiXactMember *members);
 static MultiXactId GetNewMultiXactId(int nmembers, MultiXactOffset *offset);
@@ -672,7 +671,7 @@ ReadNextMultiXactId(void)
  *
  * NB: the passed members[] array will be sorted in-place.
  */
-static MultiXactId
+MultiXactId
 CreateMultiXactId(int nmembers, MultiXactMember *members)
 {
 	MultiXactId multi;
diff --git a/src/backend/commands/vacuumlazy.c b/src/backend/commands/vacuumlazy.c
index fe2d9e7..538f3b8 100644
--- a/src/backend/commands/vacuumlazy.c
+++ b/src/backend/commands/vacuumlazy.c
@@ -500,13 +500,14 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 		bool		tupgone,
 					hastup;
 		int			prev_dead_count;
-		OffsetNumber frozen[MaxOffsetNumber];
+		xl_heap_freeze_tuple frozen[MaxOffsetNumber]; /* FIXME: stack ok? */
 		int			nfrozen;
 		Size		freespace;
 		bool		all_visible_according_to_vm;
 		bool		all_visible;
 		bool		has_dead_tuples;
 		TransactionId visibility_cutoff_xid = InvalidTransactionId;
+		int			i;
 
 		if (blkno == next_not_all_visible_block)
 		{
@@ -894,9 +895,9 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 				 * Each non-removable tuple must be checked to see if it needs
 				 * freezing.  Note we already have exclusive buffer lock.
 				 */
-				if (heap_freeze_tuple(tuple.t_data, FreezeLimit,
-									  MultiXactCutoff))
-					frozen[nfrozen++] = offnum;
+				if (heap_prepare_freeze_tuple(tuple.t_data, FreezeLimit,
+											  MultiXactCutoff, &frozen[nfrozen]))
+					frozen[nfrozen++].off = offnum;
 			}
 		}						/* scan along page */
 
@@ -907,15 +908,32 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 		 */
 		if (nfrozen > 0)
 		{
+			START_CRIT_SECTION();
+
 			MarkBufferDirty(buf);
+
+			/* execute collected freezes */
+			for (i = 0; i < nfrozen; i++)
+			{
+				ItemId		itemid;
+				HeapTupleHeader htup;
+
+				itemid = PageGetItemId(page, frozen[i].off);
+				htup = (HeapTupleHeader) PageGetItem(page, itemid);
+
+				heap_execute_freeze_tuple(htup, &frozen[i]);
+			}
+
+			/* Now WAL-log freezing if neccessary */
 			if (RelationNeedsWAL(onerel))
 			{
 				XLogRecPtr	recptr;
 
 				recptr = log_heap_freeze(onerel, buf, FreezeLimit,
-										 MultiXactCutoff, frozen, nfrozen);
+										 frozen, nfrozen);
 				PageSetLSN(page, recptr);
 			}
+			END_CRIT_SECTION();
 		}
 
 		/*
diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index 1ebc5ff..67d5fec 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -598,11 +598,13 @@ HeapTupleSatisfiesUpdate(HeapTuple htup, CommandId curcid,
 
 		/* no member, even just a locker, alive anymore */
 		if (!MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
+		{
 			SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 						InvalidTransactionId);
+			return HeapTupleMayBeUpdated;
+		}
 
-		/* it must have aborted or crashed */
-		return HeapTupleMayBeUpdated;
+		return HeapTupleBeingUpdated;
 	}
 
 	if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h
index 0d40398..e5864bb 100644
--- a/src/include/access/heapam.h
+++ b/src/include/access/heapam.h
@@ -148,8 +148,13 @@ extern HTSU_Result heap_lock_tuple(Relation relation, HeapTuple tuple,
 				bool follow_update,
 				Buffer *buffer, HeapUpdateFailureData *hufd);
 extern void heap_inplace_update(Relation relation, HeapTuple tuple);
+
+struct xl_heap_freeze_tuple;
 extern bool heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
-				  TransactionId cutoff_multi);
+					  TransactionId cutoff_multi);
+extern bool heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+					  TransactionId cutoff_multi, struct xl_heap_freeze_tuple *frz);
+extern void heap_execute_freeze_tuple(HeapTupleHeader tuple, struct xl_heap_freeze_tuple *xlrec_tp);
 extern bool heap_tuple_needs_freeze(HeapTupleHeader tuple, TransactionId cutoff_xid,
 						MultiXactId cutoff_multi, Buffer buf);
 
diff --git a/src/include/access/heapam_xlog.h b/src/include/access/heapam_xlog.h
index 4381778..d2baa5b 100644
--- a/src/include/access/heapam_xlog.h
+++ b/src/include/access/heapam_xlog.h
@@ -50,7 +50,7 @@
  */
 #define XLOG_HEAP2_FREEZE		0x00
 #define XLOG_HEAP2_CLEAN		0x10
-/* 0x20 is free, was XLOG_HEAP2_CLEAN_MOVE */
+#define XLOG_HEAP2_FREEZE_PAGE	0x20
 #define XLOG_HEAP2_CLEANUP_INFO 0x30
 #define XLOG_HEAP2_VISIBLE		0x40
 #define XLOG_HEAP2_MULTI_INSERT 0x50
@@ -251,6 +251,33 @@ typedef struct xl_heap_freeze
 
 #define SizeOfHeapFreeze (offsetof(xl_heap_freeze, cutoff_multi) + sizeof(MultiXactId))
 
+/* This is what we need to know about tuple freezing during vacuum */
+typedef struct xl_heap_freeze_tuple
+{
+	OffsetNumber off;
+	bool freeze_xmin;
+	bool invalid_xvac;
+	bool freeze_xvac;
+	TransactionId xmax;
+	uint16		t_infomask2;
+	uint16		t_infomask;
+} xl_heap_freeze_tuple;
+
+#define SizeOfHeapFreezeTuple sizeof(xl_heap_freeze_tuple)
+
+/* This is what we need to know about tuple freezing during vacuum */
+typedef struct xl_heap_freeze_block
+{
+	RelFileNode node;
+	BlockNumber block;
+	TransactionId cutoff_xid;
+	uint16		ntuples;
+	xl_heap_freeze_tuple tuples[1];
+} xl_heap_freeze_page;
+
+#define MinSizeOfHeapFreezeBlock (offsetof(xl_heap_freeze_block, tuples))
+
+
 /* This is what we need to know about setting a visibility map bit */
 typedef struct xl_heap_visible
 {
@@ -277,8 +304,7 @@ extern XLogRecPtr log_heap_clean(Relation reln, Buffer buffer,
 			   OffsetNumber *nowunused, int nunused,
 			   TransactionId latestRemovedXid);
 extern XLogRecPtr log_heap_freeze(Relation reln, Buffer buffer,
-				TransactionId cutoff_xid, MultiXactId cutoff_multi,
-				OffsetNumber *offsets, int offcnt);
+		  TransactionId cutoff_xid,	xl_heap_freeze_tuple *tuples, int ntuples);
 extern XLogRecPtr log_heap_visible(RelFileNode rnode, Buffer heap_buffer,
 				 Buffer vm_buffer, TransactionId cutoff_xid);
 extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index 6085ea3..cad91e2 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -79,6 +79,7 @@ typedef struct xl_multixact_create
 extern MultiXactId MultiXactIdCreate(TransactionId xid1,
 				  MultiXactStatus status1, TransactionId xid2,
 				  MultiXactStatus status2);
+extern MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members);
 extern MultiXactId MultiXactIdExpand(MultiXactId multi, TransactionId xid,
 				  MultiXactStatus status);
 extern MultiXactId ReadNextMultiXactId(void);
-- 
1.8.5.rc2.dirty

*** a/src/backend/utils/time/tqual.c
--- b/src/backend/utils/time/tqual.c
***************
*** 789,801 **** HeapTupleSatisfiesUpdate(HeapTupleHeader tuple, CommandId curcid,
  		if (TransactionIdDidCommit(xmax))
  			return HeapTupleUpdated;
  
! 		/* no member, even just a locker, alive anymore */
  		if (!MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
  			SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
  						InvalidTransactionId);
! 
! 		/* it must have aborted or crashed */
! 		return HeapTupleMayBeUpdated;
  	}
  
  	if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
--- 789,814 ----
  		if (TransactionIdDidCommit(xmax))
  			return HeapTupleUpdated;
  
! 		/*
! 		 * By here, the update in the Xmax is either aborted or crashed, but
! 		 * what about the other members?
! 		 */
! 
  		if (!MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
+ 		{
+ 			/*
+ 			 * There's no member, even just a locker, alive anymore, so we can
+ 			 * mark the Xmax as invalid.
+ 			 */
  			SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
  						InvalidTransactionId);
! 			return HeapTupleMayBeUpdated;
! 		}
! 		else
! 		{
! 			/* There are lockers running */
! 			return HeapTupleBeingUpdated;
! 		}
  	}
  
  	if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
*** a/src/test/isolation/expected/delete-abort-savept.out
--- b/src/test/isolation/expected/delete-abort-savept.out
***************
*** 23,33 **** key            value
  step s1svp: SAVEPOINT f;
  step s1d: DELETE FROM foo;
  step s1r: ROLLBACK TO f;
! step s2l: SELECT * FROM foo FOR UPDATE;
  key            value          
  
  1              1              
- step s1c: COMMIT;
  step s2c: COMMIT;
  
  starting permutation: s1l s1svp s1d s1r s2l s2c s1c
--- 23,34 ----
  step s1svp: SAVEPOINT f;
  step s1d: DELETE FROM foo;
  step s1r: ROLLBACK TO f;
! step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
! step s1c: COMMIT;
! step s2l: <... completed>
  key            value          
  
  1              1              
  step s2c: COMMIT;
  
  starting permutation: s1l s1svp s1d s1r s2l s2c s1c
***************
*** 38,49 **** key            value
  step s1svp: SAVEPOINT f;
  step s1d: DELETE FROM foo;
  step s1r: ROLLBACK TO f;
! step s2l: SELECT * FROM foo FOR UPDATE;
! key            value          
! 
! 1              1              
! step s2c: COMMIT;
! step s1c: COMMIT;
  
  starting permutation: s1l s1svp s1d s2l s1r s1c s2c
  step s1l: SELECT * FROM foo FOR KEY SHARE;
--- 39,46 ----
  step s1svp: SAVEPOINT f;
  step s1d: DELETE FROM foo;
  step s1r: ROLLBACK TO f;
! step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
! invalid permutation detected
  
  starting permutation: s1l s1svp s1d s2l s1r s1c s2c
  step s1l: SELECT * FROM foo FOR KEY SHARE;
*** /dev/null
--- b/src/test/isolation/expected/multixact-no-forget.out
***************
*** 0 ****
--- 1,28 ----
+ Parsed test spec with 3 sessions
+ 
+ starting permutation: s1_lock s2_update s2_abort s3_lock s1_commit
+ step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+ value          
+ 
+ 1              
+ step s2_update: UPDATE dont_forget SET value = 2;
+ step s2_abort: ROLLBACK;
+ step s3_lock: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+ step s1_commit: COMMIT;
+ step s3_lock: <... completed>
+ value          
+ 
+ 
+ starting permutation: s1_lock s2_update s2_commit s3_lock s1_commit
+ step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+ value          
+ 
+ 1              
+ step s2_update: UPDATE dont_forget SET value = 2;
+ step s2_commit: COMMIT;
+ step s3_lock: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+ step s1_commit: COMMIT;
+ step s3_lock: <... completed>
+ value          
+ 
+ 2              
*** /dev/null
--- b/src/test/isolation/expected/multixact-no-forget_1.out
***************
*** 0 ****
--- 1,27 ----
+ Parsed test spec with 3 sessions
+ 
+ starting permutation: s1_lock s2_update s2_abort s3_lock s1_commit
+ step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+ value          
+ 
+ 1              
+ step s2_update: UPDATE dont_forget SET value = 2;
+ step s2_abort: ROLLBACK;
+ step s3_lock: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+ step s1_commit: COMMIT;
+ step s3_lock: <... completed>
+ error in steps s1_commit s3_lock: ERROR:  could not serialize access due to concurrent update
+ 
+ starting permutation: s1_lock s2_update s2_commit s3_lock s1_commit
+ step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+ value          
+ 
+ 1              
+ step s2_update: UPDATE dont_forget SET value = 2;
+ step s2_commit: COMMIT;
+ step s3_lock: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+ step s1_commit: COMMIT;
+ step s3_lock: <... completed>
+ value          
+ 
+ 2              
*** a/src/test/isolation/isolation_schedule
--- b/src/test/isolation/isolation_schedule
***************
*** 20,24 **** test: delete-abort-savept
--- 20,25 ----
  test: delete-abort-savept-2
  test: aborted-keyrevoke
  test: multixact-no-deadlock
+ test: multixact-no-forget
  test: drop-index-concurrently-1
  test: timeouts
*** /dev/null
--- b/src/test/isolation/specs/multixact-no-forget.spec
***************
*** 0 ****
--- 1,32 ----
+ # If transaction A holds a lock, and transaction B does an update,
+ # make sure we don't forget the lock if B aborts.
+ setup
+ {
+   CREATE TABLE dont_forget (
+ 	value	int
+   );
+ 
+   INSERT INTO dont_forget VALUES (1);
+ }
+ 
+ teardown
+ {
+   DROP TABLE dont_forget;
+ }
+ 
+ session "s1"
+ setup			{ BEGIN; }
+ step "s1_lock"	{ SELECT * FROM dont_forget FOR KEY SHARE; }
+ step "s1_commit" { COMMIT; }
+ 
+ session "s2"
+ setup				{ BEGIN; }
+ step "s2_update"	{ UPDATE dont_forget SET value = 2; }
+ step "s2_abort"		{ ROLLBACK; }
+ step "s2_commit"	{ COMMIT; }
+ 
+ session "s3"
+ step "s3_lock"	{ SELECT * FROM dont_forget FOR UPDATE; }
+ 
+ permutation "s1_lock" "s2_update" "s2_abort" "s3_lock" "s1_commit"
+ permutation "s1_lock" "s2_update" "s2_commit" "s3_lock" "s1_commit"

>From 48b6f5eead73a41880dd311b7a55d2b88794ca3d Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Wed, 4 Dec 2013 17:20:14 -0300
Subject: [PATCH 1/4] Avoid resetting Xmax when it's a multi with an aborted
 update

HeapTupleSatisfiesUpdate can very easily "forget" tuple locks while
checking the contents of a multixact and finding it contains an aborted
update, by setting the HEAP_XMAX_INVALID bit.  This would lead to
concurrent transactions not noticing any previous locks held by
transactions that might still be running, and thus being able to acquire
subsequent locks they wouldn't be normally able to acquire.

This bug was introduced in commit 1ce150b7bb; backpatch this fix to 9.3,
like that commit.

This change reverts the change to the delete-abort-savept isolation test
in 1ce150b7bb, because that behavior change was caused by this bug.

Noticed by Andres Freund while investigating a different issue reported
by Noah Misch.
---
 src/backend/utils/time/tqual.c                     |   21 ++++++++++++++++----
 .../isolation/expected/delete-abort-savept.out     |   13 +++++-------
 2 files changed, 22 insertions(+), 12 deletions(-)

diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index 4d63b1c..f787f2c 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -789,13 +789,26 @@ HeapTupleSatisfiesUpdate(HeapTupleHeader tuple, CommandId curcid,
 		if (TransactionIdDidCommit(xmax))
 			return HeapTupleUpdated;
 
-		/* no member, even just a locker, alive anymore */
+		/*
+		 * By here, the update in the Xmax is either aborted or crashed, but
+		 * what about the other members?
+		 */
+
 		if (!MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
+		{
+			/*
+			 * There's no member, even just a locker, alive anymore, so we can
+			 * mark the Xmax as invalid.
+			 */
 			SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
 						InvalidTransactionId);
-
-		/* it must have aborted or crashed */
-		return HeapTupleMayBeUpdated;
+			return HeapTupleMayBeUpdated;
+		}
+		else
+		{
+			/* There are lockers running */
+			return HeapTupleBeingUpdated;
+		}
 	}
 
 	if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
diff --git a/src/test/isolation/expected/delete-abort-savept.out b/src/test/isolation/expected/delete-abort-savept.out
index 5b8c444..3420cf4 100644
--- a/src/test/isolation/expected/delete-abort-savept.out
+++ b/src/test/isolation/expected/delete-abort-savept.out
@@ -23,11 +23,12 @@ key            value
 step s1svp: SAVEPOINT f;
 step s1d: DELETE FROM foo;
 step s1r: ROLLBACK TO f;
-step s2l: SELECT * FROM foo FOR UPDATE;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1c: COMMIT;
+step s2l: <... completed>
 key            value          
 
 1              1              
-step s1c: COMMIT;
 step s2c: COMMIT;
 
 starting permutation: s1l s1svp s1d s1r s2l s2c s1c
@@ -38,12 +39,8 @@ key            value
 step s1svp: SAVEPOINT f;
 step s1d: DELETE FROM foo;
 step s1r: ROLLBACK TO f;
-step s2l: SELECT * FROM foo FOR UPDATE;
-key            value          
-
-1              1              
-step s2c: COMMIT;
-step s1c: COMMIT;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+invalid permutation detected
 
 starting permutation: s1l s1svp s1d s2l s1r s1c s2c
 step s1l: SELECT * FROM foo FOR KEY SHARE;
-- 
1.7.10.4

>From fbe641eeb7eb535c1cac422e3f5962928e3b0362 Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Wed, 4 Dec 2013 17:26:07 -0300
Subject: [PATCH 2/4] Fix improper abort during update chain locking

In 247c76a98909, I added some code to do fine-grained checking of
MultiXact status of locking/updating transactions when traversing an
update chain.  There was a thinko in that patch which would have the
traversing abort, that is return HeapTupleUpdated, when the other
transaction is a committed lock-only.  In this case we should ignore it
and return success instead.  Of course, in the case where there is a
committed update, HeapTupleUpdated is the correct return value.

A user-visible symptom of this bug is that in REPEATABLE READ and
SERIALIZABLE transaction isolation modes spurious serializability errors
can occur:
  ERROR:  could not serialize access due to concurrent update

In order for this to happen, there needs to be a tuple that's key-share-
locked and also updated, and the update must abort; a subsequent
transaction trying to acquire a new lock on that tuple would abort with
the above error.  The reason is that the initial FOR KEY SHARE is seen
as committed by the new locking transaction, which triggers this bug.

The isolation test added by this commit illustrates the desired
behavior.

Backpatch to 9.3.
---
 src/backend/access/heap/heapam.c                   |   19 ++-
 .../isolation/expected/multixact-no-forget.out     |  122 ++++++++++++++++++++
 .../isolation/expected/multixact-no-forget_1.out   |  118 +++++++++++++++++++
 src/test/isolation/specs/multixact-no-forget.spec  |   42 +++++++
 4 files changed, 298 insertions(+), 3 deletions(-)
 create mode 100644 src/test/isolation/expected/multixact-no-forget.out
 create mode 100644 src/test/isolation/expected/multixact-no-forget_1.out
 create mode 100644 src/test/isolation/specs/multixact-no-forget.spec

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 64174b6..1a0dd21 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -4842,10 +4842,23 @@ test_lockmode_for_conflict(MultiXactStatus status, TransactionId xid,
 	else if (TransactionIdDidCommit(xid))
 	{
 		/*
-		 * If the updating transaction committed, what we do depends on whether
-		 * the lock modes conflict: if they do, then we must report error to
-		 * caller.  But if they don't, we can fall through to lock it.
+		 * The other transaction committed.  If it was only a locker, then the
+		 * lock is completely gone now and we can return success; but if it
+		 * was an update, then what we do depends on whether the two lock
+		 * modes conflict.	If they conflict, then we must report error to
+		 * caller. But if they don't, we can fall through to allow the current
+		 * transaction to lock the tuple.
+		 *
+		 * Note: the reason we worry about ISUPDATE here is because as soon as
+		 * a transaction ends, all its locks are gone and meaningless, and
+		 * thus we can ignore them; whereas its updates persist.  In the
+		 * TransactionIdIsInProgress case, above, we don't need to check
+		 * because we know the lock is still "alive" and thus a conflict needs
+		 * always be checked.
 		 */
+		if (!ISUPDATE_from_mxstatus(status))
+			return HeapTupleMayBeUpdated;
+
 		if (DoLockModesConflict(LOCKMODE_from_mxstatus(status),
 								LOCKMODE_from_mxstatus(wantedstatus)))
 			/* bummer */
diff --git a/src/test/isolation/expected/multixact-no-forget.out b/src/test/isolation/expected/multixact-no-forget.out
new file mode 100644
index 0000000..20f01a6
--- /dev/null
+++ b/src/test/isolation/expected/multixact-no-forget.out
@@ -0,0 +1,122 @@
+Parsed test spec with 3 sessions
+
+starting permutation: s1_lock s2_update s2_abort s3_forkeyshr s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_abort: ROLLBACK;
+step s3_forkeyshr: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s1_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s2_commit s3_forkeyshr s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_commit: COMMIT;
+step s3_forkeyshr: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+2              
+step s1_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s1_commit s3_forkeyshr s2_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s1_commit: COMMIT;
+step s3_forkeyshr: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s2_abort s3_fornokeyupd s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_abort: ROLLBACK;
+step s3_fornokeyupd: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+step s1_commit: COMMIT;
+step s3_fornokeyupd: <... completed>
+value          
+
+1              
+
+starting permutation: s1_lock s2_update s2_commit s3_fornokeyupd s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_commit: COMMIT;
+step s3_fornokeyupd: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+step s1_commit: COMMIT;
+step s3_fornokeyupd: <... completed>
+value          
+
+2              
+
+starting permutation: s1_lock s2_update s1_commit s3_fornokeyupd s2_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s1_commit: COMMIT;
+step s3_fornokeyupd: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+step s2_commit: COMMIT;
+step s3_fornokeyupd: <... completed>
+value          
+
+2              
+
+starting permutation: s1_lock s2_update s2_abort s3_forupd s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_abort: ROLLBACK;
+step s3_forupd: SELECT * FROM dont_forget FOR NO KEY UPDATE;
+value          
+
+1              
+step s1_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s2_commit s3_forupd s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_commit: COMMIT;
+step s3_forupd: SELECT * FROM dont_forget FOR NO KEY UPDATE;
+value          
+
+2              
+step s1_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s1_commit s3_forupd s2_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s1_commit: COMMIT;
+step s3_forupd: SELECT * FROM dont_forget FOR NO KEY UPDATE; <waiting ...>
+step s2_commit: COMMIT;
+step s3_forupd: <... completed>
+value          
+
+2              
diff --git a/src/test/isolation/expected/multixact-no-forget_1.out b/src/test/isolation/expected/multixact-no-forget_1.out
new file mode 100644
index 0000000..7c0adcf
--- /dev/null
+++ b/src/test/isolation/expected/multixact-no-forget_1.out
@@ -0,0 +1,118 @@
+Parsed test spec with 3 sessions
+
+starting permutation: s1_lock s2_update s2_abort s3_forkeyshr s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_abort: ROLLBACK;
+step s3_forkeyshr: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s1_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s2_commit s3_forkeyshr s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_commit: COMMIT;
+step s3_forkeyshr: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+2              
+step s1_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s1_commit s3_forkeyshr s2_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s1_commit: COMMIT;
+step s3_forkeyshr: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s2_abort s3_fornokeyupd s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_abort: ROLLBACK;
+step s3_fornokeyupd: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+step s1_commit: COMMIT;
+step s3_fornokeyupd: <... completed>
+value          
+
+1              
+
+starting permutation: s1_lock s2_update s2_commit s3_fornokeyupd s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_commit: COMMIT;
+step s3_fornokeyupd: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+step s1_commit: COMMIT;
+step s3_fornokeyupd: <... completed>
+value          
+
+2              
+
+starting permutation: s1_lock s2_update s1_commit s3_fornokeyupd s2_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s1_commit: COMMIT;
+step s3_fornokeyupd: SELECT * FROM dont_forget FOR UPDATE; <waiting ...>
+step s2_commit: COMMIT;
+step s3_fornokeyupd: <... completed>
+error in steps s2_commit s3_fornokeyupd: ERROR:  could not serialize access due to concurrent update
+
+starting permutation: s1_lock s2_update s2_abort s3_forupd s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_abort: ROLLBACK;
+step s3_forupd: SELECT * FROM dont_forget FOR NO KEY UPDATE;
+value          
+
+1              
+step s1_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s2_commit s3_forupd s1_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s2_commit: COMMIT;
+step s3_forupd: SELECT * FROM dont_forget FOR NO KEY UPDATE;
+value          
+
+2              
+step s1_commit: COMMIT;
+
+starting permutation: s1_lock s2_update s1_commit s3_forupd s2_commit
+step s1_lock: SELECT * FROM dont_forget FOR KEY SHARE;
+value          
+
+1              
+step s2_update: UPDATE dont_forget SET value = 2;
+step s1_commit: COMMIT;
+step s3_forupd: SELECT * FROM dont_forget FOR NO KEY UPDATE; <waiting ...>
+step s2_commit: COMMIT;
+step s3_forupd: <... completed>
+error in steps s2_commit s3_forupd: ERROR:  could not serialize access due to concurrent update
diff --git a/src/test/isolation/specs/multixact-no-forget.spec b/src/test/isolation/specs/multixact-no-forget.spec
new file mode 100644
index 0000000..c1cfb7c
--- /dev/null
+++ b/src/test/isolation/specs/multixact-no-forget.spec
@@ -0,0 +1,42 @@
+# If transaction A holds a lock, and transaction B does an update,
+# make sure we don't forget the lock if B aborts.
+setup
+{
+  CREATE TABLE dont_forget (
+	value	int
+  );
+
+  INSERT INTO dont_forget VALUES (1);
+}
+
+teardown
+{
+  DROP TABLE dont_forget;
+}
+
+session "s1"
+setup			{ BEGIN; }
+step "s1_lock"	{ SELECT * FROM dont_forget FOR KEY SHARE; }
+step "s1_commit" { COMMIT; }
+
+session "s2"
+setup				{ BEGIN; }
+step "s2_update"	{ UPDATE dont_forget SET value = 2; }
+step "s2_abort"		{ ROLLBACK; }
+step "s2_commit"	{ COMMIT; }
+
+session "s3"
+# try cases with both a non-conflicting lock with s1's and a conflicting one
+step "s3_forkeyshr"	{ SELECT * FROM dont_forget FOR KEY SHARE; }
+step "s3_fornokeyupd"	{ SELECT * FROM dont_forget FOR UPDATE; }
+step "s3_forupd"	{ SELECT * FROM dont_forget FOR NO KEY UPDATE; }
+
+permutation "s1_lock" "s2_update" "s2_abort" "s3_forkeyshr" "s1_commit"
+permutation "s1_lock" "s2_update" "s2_commit" "s3_forkeyshr" "s1_commit"
+permutation "s1_lock" "s2_update" "s1_commit" "s3_forkeyshr" "s2_commit"
+permutation "s1_lock" "s2_update" "s2_abort" "s3_fornokeyupd" "s1_commit"
+permutation "s1_lock" "s2_update" "s2_commit" "s3_fornokeyupd" "s1_commit"
+permutation "s1_lock" "s2_update" "s1_commit" "s3_fornokeyupd" "s2_commit"
+permutation "s1_lock" "s2_update" "s2_abort" "s3_forupd" "s1_commit"
+permutation "s1_lock" "s2_update" "s2_commit" "s3_forupd" "s1_commit"
+permutation "s1_lock" "s2_update" "s1_commit" "s3_forupd" "s2_commit"
-- 
1.7.10.4

*** a/src/backend/access/heap/heapam.c
--- b/src/backend/access/heap/heapam.c
***************
*** 5238,5251 **** heap_inplace_update(Relation relation, HeapTuple tuple)
  		CacheInvalidateHeapTuple(relation, tuple, NULL);
  }
  
  
  /*
!  * heap_freeze_tuple
   *
   * Check to see whether any of the XID fields of a tuple (xmin, xmax, xvac)
!  * are older than the specified cutoff XID.  If so, replace them with
!  * FrozenTransactionId or InvalidTransactionId as appropriate, and return
!  * TRUE.  Return FALSE if nothing was changed.
   *
   * It is assumed that the caller has checked the tuple with
   * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
--- 5238,5448 ----
  		CacheInvalidateHeapTuple(relation, tuple, NULL);
  }
  
+ #define		FRM_NOOP				0x0001
+ #define		FRM_INVALIDATE_XMAX		0x0002
+ #define		FRM_RETURN_IS_XID		0x0004
+ #define		FRM_RETURN_IS_MULTI		0x0008
+ #define		FRM_MARK_COMMITTED		0x0010
  
  /*
!  * FreezeMultiXactId
!  *		Determine what to do during freezing when a tuple is marked by a
!  *		MultiXactId.
!  *
!  * "flags" is an output value; it's used to tell caller what to do on return.
!  *
!  * Possible flags are:
!  * FRM_NOOP
!  *		don't do anything -- keep existing Xmax
!  * FRM_INVALIDATE_XMAX
!  *		mark Xmax as InvalidTransactionId and set XMAX_INVALID flag.
!  * FRM_RETURN_IS_XID
!  *		The Xid return value is a single update Xid to set as xmax.
!  * FRM_MARK_COMMITTED
!  *		Xmax can be marked as HEAP_XMAX_COMMITTED
!  * FRM_RETURN_IS_MULTI
!  *		The return value is a new MultiXactId to set as new Xmax.
!  *		(caller must obtain proper infomask bits using GetMultiXactIdHintBits)
!  */
! static TransactionId
! FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
! 				  TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				  uint16 *flags)
! {
! 	TransactionId	xid = InvalidTransactionId;
! 	int			i;
! 	MultiXactMember *members;
! 	int			nmembers;
! 	bool	need_replace;
! 	int		nnewmembers;
! 	MultiXactMember *newmembers;
! 	bool	has_lockers;
! 	TransactionId update_xid;
! 	bool	update_committed;
! 
! 	*flags = 0;
! 
! 	if (!MultiXactIdIsValid(multi))
! 	{
! 		/* Ensure infomask bits are appropriately set/reset */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		return InvalidTransactionId;
! 	}
! 	else if (MultiXactIdPrecedes(multi, cutoff_multi))
! 	{
! 		/*
! 		 * This old multi cannot possibly have members still running.  If it
! 		 * was a locker only, it can be removed without any further
! 		 * consideration; but if it contained an update, we might need to
! 		 * preserve it.
! 		 */
! 		if (HEAP_XMAX_IS_LOCKED_ONLY(t_infomask))
! 		{
! 			*flags |= FRM_INVALIDATE_XMAX;
! 			return InvalidTransactionId;
! 		}
! 		else
! 		{
! 			/* replace multi by update xid */
! 			xid = MultiXactIdGetUpdateXid(multi, t_infomask);
! 
! 			/* wasn't only a lock, xid needs to be valid */
! 			Assert(TransactionIdIsValid(xid));
! 
! 			/*
! 			 * If the xid is older than the cutoff, it has to have aborted,
! 			 * otherwise the tuple would have gotten pruned away.
! 			 */
! 			if (TransactionIdPrecedes(xid, cutoff_xid))
! 			{
! 				Assert(!TransactionIdDidCommit(xid));
! 				*flags |= FRM_INVALIDATE_XMAX;
! 				/* xid = InvalidTransactionId; */
! 			}
! 			else
! 			{
! 				*flags |= FRM_RETURN_IS_XID;
! 			}
! 		}
! 	}
! 
! 	/*
! 	 * This multixact might have or might not have members still running,
! 	 * but we know it's valid and is newer than the cutoff point for
! 	 * multis.  However, some member(s) of it may be below the cutoff for
! 	 * Xids, so we need to walk the whole members array to figure out what
! 	 * to do, if anything.
! 	 */
! 
! 	nmembers = GetMultiXactIdMembers(multi, &members, false);
! 	if (nmembers <= 0)
! 	{
! 		/* Nothing worth keeping */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		return InvalidTransactionId;
! 	}
! 
! 	/* is there anything older than the cutoff? */
! 	need_replace = false;
! 	for (i = 0; i < nmembers; i++)
! 	{
! 		if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
! 		{
! 			need_replace = true;
! 			break;
! 		}
! 	}
! 
! 	/*
! 	 * In the simplest case, there is no member older than the cutoff; we can
! 	 * keep the existing MultiXactId as is.
! 	 */
! 	if (!need_replace)
! 	{
! 		*flags |= FRM_NOOP;
! 		pfree(members);
! 		return InvalidTransactionId;
! 	}
! 
! 	/*
! 	 * If the multi needs to be updated, figure out which members do we need
! 	 * to keep.
! 	 */
! 	nnewmembers = 0;
! 	newmembers = palloc(sizeof(MultiXactMember) * nmembers);
! 	has_lockers = false;
! 	update_xid = InvalidTransactionId;
! 	update_committed = false;
! 
! 	for (i = 0; i < nmembers; i++)
! 	{
! 		if (ISUPDATE_from_mxstatus(members[i].status) &&
! 			!TransactionIdDidAbort(members[i].xid))
! 		{
! 			/* if it's an update, we must keep unless it aborted */
! 			newmembers[nnewmembers++] = members[i];
! 			Assert(!TransactionIdIsValid(update_xid));
! 			update_xid = members[i].xid;
! 			/* tell caller to set hint while we have the Xid in cache */
! 			if (TransactionIdDidCommit(update_xid))
! 				update_committed = true;
! 		}
! 
! 		/* We only keep lockers if they are still running */
! 		if (TransactionIdIsCurrentTransactionId(members[i].xid) ||
! 			TransactionIdIsInProgress(members[i].xid))
! 		{
! 			newmembers[nnewmembers++] = members[i];
! 			has_lockers = true;
! 		}
! 	}
! 
! 	pfree(members);
! 
! 	if (nnewmembers == 0)
! 	{
! 		/* nothing worth keeping!? Tell caller to remove the whole thing */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		xid = InvalidTransactionId;
! 	}
! 	else if (TransactionIdIsValid(update_xid) && !has_lockers)
! 	{
! 		/*
! 		 * If there's a single member and it's an update, pass it back alone
! 		 * without creating a new Multi.  (XXX we could do this when there's a
! 		 * single remaining locker, too, but that would complicate the API too
! 		 * much; moreover, the case with the single updater is more
! 		 * interesting, because those are longer-lived.)
! 		 */
! 		Assert(nnewmembers == 1);
! 		*flags |= FRM_RETURN_IS_XID;
! 		if (update_committed)
! 			*flags |= FRM_MARK_COMMITTED;
! 		xid = update_xid;
! 	}
! 	else
! 	{
! 		/* Note this is WAL-logged */
! 		xid = CreateMultiXactId(nnewmembers, newmembers);
! 		*flags |= FRM_RETURN_IS_MULTI;
! 	}
! 
! 	pfree(newmembers);
! 
! 	return xid;
! }
! 
! /*
!  * heap_prepare_freeze_tuple
   *
   * Check to see whether any of the XID fields of a tuple (xmin, xmax, xvac)
!  * are older than the specified cutoff XID and cutoff MultiXactId.  If so,
!  * setup enough state (in the *frz output argument) to later execute and
!  * WAL-log what we would need to do, and return TRUE.  Return FALSE if nothing
!  * is to be changed.
!  *
!  * Caller is responsible for setting the offset field, if appropriate.  This
!  * is only necessary if the freeze is to be WAL-logged.
   *
   * It is assumed that the caller has checked the tuple with
   * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
***************
*** 5254,5307 **** heap_inplace_update(Relation relation, HeapTuple tuple)
   * NB: cutoff_xid *must* be <= the current global xmin, to ensure that any
   * XID older than it could neither be running nor seen as running by any
   * open transaction.  This ensures that the replacement will not change
!  * anyone's idea of the tuple state.  Also, since we assume the tuple is
!  * not HEAPTUPLE_DEAD, the fact that an XID is not still running allows us
!  * to assume that it is either committed good or aborted, as appropriate;
!  * so we need no external state checks to decide what to do.  (This is good
!  * because this function is applied during WAL recovery, when we don't have
!  * access to any such state, and can't depend on the hint bits to be set.)
!  * There is an exception we make which is to assume GetMultiXactIdMembers can
!  * be called during recovery.
!  *
   * Similarly, cutoff_multi must be less than or equal to the smallest
   * MultiXactId used by any transaction currently open.
   *
   * If the tuple is in a shared buffer, caller must hold an exclusive lock on
   * that buffer.
   *
!  * Note: it might seem we could make the changes without exclusive lock, since
!  * TransactionId read/write is assumed atomic anyway.  However there is a race
!  * condition: someone who just fetched an old XID that we overwrite here could
!  * conceivably not finish checking the XID against pg_clog before we finish
!  * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
!  * exclusive lock ensures no other backend is in process of checking the
!  * tuple status.  Also, getting exclusive lock makes it safe to adjust the
!  * infomask bits.
!  *
!  * NB: Cannot rely on hint bits here, they might not be set after a crash or
!  * on a standby.
   */
  bool
! heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
! 				  MultiXactId cutoff_multi)
  {
  	bool		changed = false;
  	bool		freeze_xmax = false;
  	TransactionId xid;
  
  	/* Process xmin */
  	xid = HeapTupleHeaderGetXmin(tuple);
  	if (TransactionIdIsNormal(xid) &&
  		TransactionIdPrecedes(xid, cutoff_xid))
  	{
! 		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
! 
  		/*
  		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
  		 * already be set here, but there's a small chance not.
  		 */
! 		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
  		changed = true;
  	}
  
--- 5451,5492 ----
   * NB: cutoff_xid *must* be <= the current global xmin, to ensure that any
   * XID older than it could neither be running nor seen as running by any
   * open transaction.  This ensures that the replacement will not change
!  * anyone's idea of the tuple state.
   * Similarly, cutoff_multi must be less than or equal to the smallest
   * MultiXactId used by any transaction currently open.
   *
   * If the tuple is in a shared buffer, caller must hold an exclusive lock on
   * that buffer.
   *
!  * NB: It is not enough to set hint bits to indicate something is
!  * committed/invalid -- they might not be set on a standby, or after crash
!  * recovery.  We really need to remove old xids.
   */
  bool
! heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
! 						  TransactionId cutoff_multi, xl_heap_freeze_tuple *frz)
! 
  {
  	bool		changed = false;
  	bool		freeze_xmax = false;
  	TransactionId xid;
  
+ 	frz->frzflags = 0;
+ 	frz->t_infomask2 = tuple->t_infomask2;
+ 	frz->t_infomask = tuple->t_infomask;
+ 	frz->xmax = HeapTupleHeaderGetRawXmax(tuple);
+ 
  	/* Process xmin */
  	xid = HeapTupleHeaderGetXmin(tuple);
  	if (TransactionIdIsNormal(xid) &&
  		TransactionIdPrecedes(xid, cutoff_xid))
  	{
! 		frz->frzflags |= XLH_FREEZE_XMIN;
  		/*
  		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
  		 * already be set here, but there's a small chance not.
  		 */
! 		frz->t_infomask |= HEAP_XMIN_COMMITTED;
  		changed = true;
  	}
  
***************
*** 5318,5408 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  
  	if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
  	{
! 		if (!MultiXactIdIsValid(xid))
! 		{
! 			/* no xmax set, ignore */
! 			;
! 		}
! 		else if (MultiXactIdPrecedes(xid, cutoff_multi))
! 		{
! 			/*
! 			 * This old multi cannot possibly be running.  If it was a locker
! 			 * only, it can be removed without much further thought; but if it
! 			 * contained an update, we need to preserve it.
! 			 */
! 			if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
! 				freeze_xmax = true;
! 			else
! 			{
! 				TransactionId update_xid;
  
! 				update_xid = HeapTupleGetUpdateXid(tuple);
  
! 				/*
! 				 * The multixact has an update hidden within.  Get rid of it.
! 				 *
! 				 * If the update_xid is below the cutoff_xid, it necessarily
! 				 * must be an aborted transaction.  In a primary server, such
! 				 * an Xmax would have gotten marked invalid by
! 				 * HeapTupleSatisfiesVacuum, but in a replica that is not
! 				 * called before we are, so deal with it in the same way.
! 				 *
! 				 * If not below the cutoff_xid, then the tuple would have been
! 				 * pruned by vacuum, if the update committed long enough ago,
! 				 * and we wouldn't be freezing it; so it's either recently
! 				 * committed, or in-progress.  Deal with this by setting the
! 				 * Xmax to the update Xid directly and remove the IS_MULTI
! 				 * bit.  (We know there cannot be running lockers in this
! 				 * multi, because it's below the cutoff_multi value.)
! 				 */
! 
! 				if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 				{
! 					Assert(InRecovery || TransactionIdDidAbort(update_xid));
! 					freeze_xmax = true;
! 				}
! 				else
! 				{
! 					Assert(InRecovery || !TransactionIdIsInProgress(update_xid));
! 					tuple->t_infomask &= ~HEAP_XMAX_BITS;
! 					HeapTupleHeaderSetXmax(tuple, update_xid);
! 					changed = true;
! 				}
! 			}
! 		}
! 		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
  		{
! 			/* newer than the cutoff, so don't touch it */
  			;
  		}
! 		else
  		{
! 			TransactionId	update_xid;
  
! 			/*
! 			 * This is a multixact which is not marked LOCK_ONLY, but which
! 			 * is newer than the cutoff_multi.  If the update_xid is below the
! 			 * cutoff_xid point, then we can just freeze the Xmax in the
! 			 * tuple, removing it altogether.  This seems simple, but there
! 			 * are several underlying assumptions:
! 			 *
! 			 * 1. A tuple marked by an multixact containing a very old
! 			 * committed update Xid would have been pruned away by vacuum; we
! 			 * wouldn't be freezing this tuple at all.
! 			 *
! 			 * 2. There cannot possibly be any live locking members remaining
! 			 * in the multixact.  This is because if they were alive, the
! 			 * update's Xid would had been considered, via the lockers'
! 			 * snapshot's Xmin, as part the cutoff_xid.
! 			 *
! 			 * 3. We don't create new MultiXacts via MultiXactIdExpand() that
! 			 * include a very old aborted update Xid: in that function we only
! 			 * include update Xids corresponding to transactions that are
! 			 * committed or in-progress.
! 			 */
! 			update_xid = HeapTupleGetUpdateXid(tuple);
! 			if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 				freeze_xmax = true;
  		}
  	}
  	else if (TransactionIdIsNormal(xid) &&
--- 5503,5536 ----
  
  	if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
  	{
! 		TransactionId	newxmax;
! 		uint16	flags;
  
! 		newxmax = FreezeMultiXactId(xid, tuple->t_infomask,
! 									cutoff_xid, cutoff_multi, &flags);
  
! 		if (flags & FRM_NOOP)
  		{
! 			/* nothing to do in this case */
  			;
  		}
! 		if (flags & FRM_INVALIDATE_XMAX)
! 			freeze_xmax = true;
! 		else if (flags & FRM_RETURN_IS_XID)
  		{
! 			frz->t_infomask &= ~HEAP_XMAX_BITS;
! 			frz->xmax = newxmax;
! 			if (flags & FRM_MARK_COMMITTED)
! 				frz->t_infomask &= HEAP_XMAX_COMMITTED;
! 		}
! 		else if (flags & FRM_RETURN_IS_MULTI)
! 		{
! 			frz->t_infomask &= ~HEAP_XMAX_BITS;
! 			frz->xmax = newxmax;
  
! 			GetMultiXactIdHintBits(newxmax,
! 								   &frz->t_infomask,
! 								   &frz->t_infomask2);
  		}
  	}
  	else if (TransactionIdIsNormal(xid) &&
***************
*** 5413,5429 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  
  	if (freeze_xmax)
  	{
! 		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
  
  		/*
  		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
  		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
  		 * Also get rid of the HEAP_KEYS_UPDATED bit.
  		 */
! 		tuple->t_infomask &= ~HEAP_XMAX_BITS;
! 		tuple->t_infomask |= HEAP_XMAX_INVALID;
! 		HeapTupleHeaderClearHotUpdated(tuple);
! 		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
  		changed = true;
  	}
  
--- 5541,5557 ----
  
  	if (freeze_xmax)
  	{
! 		frz->xmax = InvalidTransactionId;
  
  		/*
  		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
  		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
  		 * Also get rid of the HEAP_KEYS_UPDATED bit.
  		 */
! 		frz->t_infomask &= ~HEAP_XMAX_BITS;
! 		frz->t_infomask |= HEAP_XMAX_INVALID;
! 		frz->t_infomask2 &= ~HEAP_HOT_UPDATED;
! 		frz->t_infomask2 &= ~HEAP_KEYS_UPDATED;
  		changed = true;
  	}
  
***************
*** 5443,5458 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  			 * xvac transaction succeeded.
  			 */
  			if (tuple->t_infomask & HEAP_MOVED_OFF)
! 				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
  			else
! 				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
  
  			/*
  			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
  			 * will already be set here, but there's a small chance not.
  			 */
  			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
  			changed = true;
  		}
  	}
--- 5571,5586 ----
  			 * xvac transaction succeeded.
  			 */
  			if (tuple->t_infomask & HEAP_MOVED_OFF)
! 				frz->frzflags |= XLH_FREEZE_XVAC;
  			else
! 				frz->frzflags |= XLH_INVALID_XVAC;
  
  			/*
  			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
  			 * will already be set here, but there's a small chance not.
  			 */
  			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 			frz->t_infomask |= HEAP_XMIN_COMMITTED;
  			changed = true;
  		}
  	}
***************
*** 5461,5466 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
--- 5589,5656 ----
  }
  
  /*
+  * heap_execute_freeze_tuple
+  *		Execute the prepared freezing of a tuple.
+  *
+  * Caller is responsible for ensuring that no other backend can access the
+  * storage underlying this tuple, either by holding an exclusive lock on the
+  * buffer containing it (which is what lazy VACUUM does), or by having it by
+  * in private storage (which is what CLUSTER and friends do).
+  *
+  * Note: it might seem we could make the changes without exclusive lock, since
+  * TransactionId read/write is assumed atomic anyway.  However there is a race
+  * condition: someone who just fetched an old XID that we overwrite here could
+  * conceivably not finish checking the XID against pg_clog before we finish
+  * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
+  * exclusive lock ensures no other backend is in process of checking the
+  * tuple status.  Also, getting exclusive lock makes it safe to adjust the
+  * infomask bits.
+  *
+  * NB: All code in here must be safe to execute during crash recovery!
+  */
+ void
+ heap_execute_freeze_tuple(HeapTupleHeader tuple, xl_heap_freeze_tuple *frz)
+ {
+ 	if (frz->frzflags & XLH_FREEZE_XMIN)
+ 		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+ 
+ 	HeapTupleHeaderSetXmax(tuple, frz->xmax);
+ 
+ 	if (frz->frzflags & XLH_FREEZE_XVAC)
+ 		HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+ 
+ 	if (frz->frzflags & XLH_INVALID_XVAC)
+ 		HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+ 
+ 	tuple->t_infomask = frz->t_infomask;
+ 	tuple->t_infomask2 = frz->t_infomask2;
+ }
+ 
+ /*
+  * heap_freeze_tuple - freeze tuple inplace without WAL logging.
+  *
+  * Useful for callers like CLUSTER that perform their own WAL logging.
+  */
+ bool
+ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+ 				  TransactionId cutoff_multi)
+ {
+ 	xl_heap_freeze_tuple frz;
+ 	bool	do_freeze;
+ 
+ 	do_freeze = heap_prepare_freeze_tuple(tuple, cutoff_xid, cutoff_multi, &frz);
+ 
+ 	/*
+ 	 * Note that because this is not a WAL-logged operation, we don't need
+ 	 * to fill in the offset in the freeze record.
+ 	 */
+ 
+ 	if (do_freeze)
+ 		heap_execute_freeze_tuple(tuple, &frz);
+ 	return do_freeze;
+ }
+ 
+ /*
   * For a given MultiXactId, return the hint bits that should be set in the
   * tuple's infomask.
   *
***************
*** 5763,5778 **** heap_tuple_needs_freeze(HeapTupleHeader tuple, TransactionId cutoff_xid,
  		}
  		else if (MultiXactIdPrecedes(multi, cutoff_multi))
  			return true;
- 		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
- 		{
- 			/* only-locker multis don't need internal examination */
- 			;
- 		}
  		else
  		{
! 			if (TransactionIdPrecedes(HeapTupleGetUpdateXid(tuple),
! 									  cutoff_xid))
! 				return true;
  		}
  	}
  	else
--- 5953,5978 ----
  		}
  		else if (MultiXactIdPrecedes(multi, cutoff_multi))
  			return true;
  		else
  		{
! 			MultiXactMember *members;
! 			int			nmembers;
! 			int		i;
! 
! 			/* need to check whether any member of the mxact is too old */
! 
! 			nmembers = GetMultiXactIdMembers(multi, &members, false);
! 
! 			for (i = 0; i < nmembers; i++)
! 			{
! 				if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
! 				{
! 					pfree(members);
! 					return true;
! 				}
! 			}
! 			if (nmembers > 0)
! 				pfree(members);
  		}
  	}
  	else
***************
*** 6022,6048 **** log_heap_clean(Relation reln, Buffer buffer,
  }
  
  /*
!  * Perform XLogInsert for a heap-freeze operation.	Caller must already
!  * have modified the buffer and marked it dirty.
   */
  XLogRecPtr
! log_heap_freeze(Relation reln, Buffer buffer,
! 				TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				OffsetNumber *offsets, int offcnt)
  {
! 	xl_heap_freeze xlrec;
  	XLogRecPtr	recptr;
  	XLogRecData rdata[2];
  
  	/* Caller should not call me on a non-WAL-logged relation */
  	Assert(RelationNeedsWAL(reln));
  	/* nor when there are no tuples to freeze */
! 	Assert(offcnt > 0);
  
  	xlrec.node = reln->rd_node;
  	xlrec.block = BufferGetBlockNumber(buffer);
  	xlrec.cutoff_xid = cutoff_xid;
! 	xlrec.cutoff_multi = cutoff_multi;
  
  	rdata[0].data = (char *) &xlrec;
  	rdata[0].len = SizeOfHeapFreeze;
--- 6222,6247 ----
  }
  
  /*
!  * Perform XLogInsert for a heap-freeze operation.	Caller must have already
!  * modified the buffer and marked it dirty.
   */
  XLogRecPtr
! log_heap_freeze(Relation reln, Buffer buffer, TransactionId cutoff_xid,
! 				xl_heap_freeze_tuple *tuples, int ntuples)
  {
! 	xl_heap_freeze_page xlrec;
  	XLogRecPtr	recptr;
  	XLogRecData rdata[2];
  
  	/* Caller should not call me on a non-WAL-logged relation */
  	Assert(RelationNeedsWAL(reln));
  	/* nor when there are no tuples to freeze */
! 	Assert(ntuples > 0);
  
  	xlrec.node = reln->rd_node;
  	xlrec.block = BufferGetBlockNumber(buffer);
  	xlrec.cutoff_xid = cutoff_xid;
! 	xlrec.ntuples = ntuples;
  
  	rdata[0].data = (char *) &xlrec;
  	rdata[0].len = SizeOfHeapFreeze;
***************
*** 6050,6066 **** log_heap_freeze(Relation reln, Buffer buffer,
  	rdata[0].next = &(rdata[1]);
  
  	/*
! 	 * The tuple-offsets array is not actually in the buffer, but pretend that
! 	 * it is.  When XLogInsert stores the whole buffer, the offsets array need
  	 * not be stored too.
  	 */
! 	rdata[1].data = (char *) offsets;
! 	rdata[1].len = offcnt * sizeof(OffsetNumber);
  	rdata[1].buffer = buffer;
  	rdata[1].buffer_std = true;
  	rdata[1].next = NULL;
  
! 	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE, rdata);
  
  	return recptr;
  }
--- 6249,6265 ----
  	rdata[0].next = &(rdata[1]);
  
  	/*
! 	 * The freeze plan array is not actually in the buffer, but pretend that
! 	 * it is.  When XLogInsert stores the whole buffer, the freeze plan need
  	 * not be stored too.
  	 */
! 	rdata[1].data = (char *) tuples;
! 	rdata[1].len = ntuples * SizeOfHeapFreezeTuple;
  	rdata[1].buffer = buffer;
  	rdata[1].buffer_std = true;
  	rdata[1].next = NULL;
  
! 	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE_PAGE, rdata);
  
  	return recptr;
  }
***************
*** 6402,6407 **** heap_xlog_clean(XLogRecPtr lsn, XLogRecord *record)
--- 6601,6699 ----
  	XLogRecordPageWithFreeSpace(xlrec->node, xlrec->block, freespace);
  }
  
+ /*
+  * Freeze a single tuple for XLOG_HEAP2_FREEZE
+  *
+  * NB: This type of record aren't generated anymore, since bugs around
+  * multixacts couldn't be fixed without a more robust type of freezing. This
+  * is kept around to be able to perform PITR.
+  */
+ static bool
+ heap_xlog_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+ 				  MultiXactId cutoff_multi)
+ {
+ 	bool		changed = false;
+ 	TransactionId xid;
+ 
+ 	xid = HeapTupleHeaderGetXmin(tuple);
+ 	if (TransactionIdIsNormal(xid) &&
+ 		TransactionIdPrecedes(xid, cutoff_xid))
+ 	{
+ 		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+ 
+ 		/*
+ 		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
+ 		 * already be set here, but there's a small chance not.
+ 		 */
+ 		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
+ 		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+ 		changed = true;
+ 	}
+ 
+ 	/*
+ 	 * Note that this code handles IS_MULTI Xmax values, too, but only to mark
+ 	 * the tuple as not updated if the multixact is below the cutoff Multixact
+ 	 * given; it doesn't remove dead members of a very old multixact.
+ 	 */
+ 	xid = HeapTupleHeaderGetRawXmax(tuple);
+ 	if ((tuple->t_infomask & HEAP_XMAX_IS_MULTI) ?
+ 		(MultiXactIdIsValid(xid) &&
+ 		 MultiXactIdPrecedes(xid, cutoff_multi)) :
+ 		(TransactionIdIsNormal(xid) &&
+ 		 TransactionIdPrecedes(xid, cutoff_xid)))
+ 	{
+ 		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
+ 
+ 		/*
+ 		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
+ 		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
+ 		 * Also get rid of the HEAP_KEYS_UPDATED bit.
+ 		 */
+ 		tuple->t_infomask &= ~HEAP_XMAX_BITS;
+ 		tuple->t_infomask |= HEAP_XMAX_INVALID;
+ 		HeapTupleHeaderClearHotUpdated(tuple);
+ 		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
+ 		changed = true;
+ 	}
+ 
+ 	/*
+ 	 * Old-style VACUUM FULL is gone, but we have to keep this code as long as
+ 	 * we support having MOVED_OFF/MOVED_IN tuples in the database.
+ 	 */
+ 	if (tuple->t_infomask & HEAP_MOVED)
+ 	{
+ 		xid = HeapTupleHeaderGetXvac(tuple);
+ 		if (TransactionIdIsNormal(xid) &&
+ 			TransactionIdPrecedes(xid, cutoff_xid))
+ 		{
+ 			/*
+ 			 * If a MOVED_OFF tuple is not dead, the xvac transaction must
+ 			 * have failed; whereas a non-dead MOVED_IN tuple must mean the
+ 			 * xvac transaction succeeded.
+ 			 */
+ 			if (tuple->t_infomask & HEAP_MOVED_OFF)
+ 				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+ 			else
+ 				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+ 
+ 			/*
+ 			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
+ 			 * will already be set here, but there's a small chance not.
+ 			 */
+ 			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
+ 			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+ 			changed = true;
+ 		}
+ 	}
+ 
+ 	return changed;
+ }
+ 
+ /*
+  * NB: This type of record aren't generated anymore, since bugs around
+  * multixacts couldn't be fixed without a more robust type of freezing. This
+  * is kept around to be able to perform PITR.
+  */
  static void
  heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
  {
***************
*** 6450,6456 **** heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
  			ItemId		lp = PageGetItemId(page, *offsets);
  			HeapTupleHeader tuple = (HeapTupleHeader) PageGetItem(page, lp);
  
! 			(void) heap_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
  			offsets++;
  		}
  	}
--- 6742,6748 ----
  			ItemId		lp = PageGetItemId(page, *offsets);
  			HeapTupleHeader tuple = (HeapTupleHeader) PageGetItem(page, lp);
  
! 			(void) heap_xlog_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
  			offsets++;
  		}
  	}
***************
*** 6574,6579 **** heap_xlog_visible(XLogRecPtr lsn, XLogRecord *record)
--- 6866,6928 ----
  	}
  }
  
+ /*
+  * Replay XLOG_HEAP2_FREEZE_PAGE records
+  */
+ static void
+ heap_xlog_freeze_page(XLogRecPtr lsn, XLogRecord *record)
+ {
+ 	xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) XLogRecGetData(record);
+ 	TransactionId cutoff_xid = xlrec->cutoff_xid;
+ 	Buffer		buffer;
+ 	Page		page;
+ 	int			ntup;
+ 
+ 	/*
+ 	 * In Hot Standby mode, ensure that there's no queries running which still
+ 	 * consider the frozen xids as running.
+ 	 */
+ 	if (InHotStandby)
+ 		ResolveRecoveryConflictWithSnapshot(cutoff_xid, xlrec->node);
+ 
+ 	/* If we have a full-page image, restore it and we're done */
+ 	if (record->xl_info & XLR_BKP_BLOCK(0))
+ 	{
+ 		(void) RestoreBackupBlock(lsn, record, 0, false, false);
+ 		return;
+ 	}
+ 
+ 	buffer = XLogReadBuffer(xlrec->node, xlrec->block, false);
+ 	if (!BufferIsValid(buffer))
+ 		return;
+ 
+ 	page = (Page) BufferGetPage(buffer);
+ 
+ 	if (lsn <= PageGetLSN(page))
+ 	{
+ 		UnlockReleaseBuffer(buffer);
+ 		return;
+ 	}
+ 
+ 	/* now execute freeze plan for each frozen tuple */
+ 	for (ntup = 0; ntup < xlrec->ntuples; ntup++)
+ 	{
+ 		xl_heap_freeze_tuple *xlrec_tp;
+ 		ItemId			lp;
+ 		HeapTupleHeader tuple;
+ 
+ 		xlrec_tp = &xlrec->tuples[ntup];
+ 		lp = PageGetItemId(page, xlrec_tp->offset);	/* offsets are one-based */
+ 		tuple = (HeapTupleHeader) PageGetItem(page, lp);
+ 
+ 		heap_execute_freeze_tuple(tuple, xlrec_tp);
+ 	}
+ 
+ 	PageSetLSN(page, lsn);
+ 	MarkBufferDirty(buffer);
+ 	UnlockReleaseBuffer(buffer);
+ }
+ 
  static void
  heap_xlog_newpage(XLogRecPtr lsn, XLogRecord *record)
  {
***************
*** 7429,7434 **** heap2_redo(XLogRecPtr lsn, XLogRecord *record)
--- 7778,7786 ----
  		case XLOG_HEAP2_CLEAN:
  			heap_xlog_clean(lsn, record);
  			break;
+ 		case XLOG_HEAP2_FREEZE_PAGE:
+ 			heap_xlog_freeze_page(lsn, record);
+ 			break;
  		case XLOG_HEAP2_CLEANUP_INFO:
  			heap_xlog_cleanup_info(lsn, record);
  			break;
*** a/src/backend/access/rmgrdesc/heapdesc.c
--- b/src/backend/access/rmgrdesc/heapdesc.c
***************
*** 149,154 **** heap2_desc(StringInfo buf, uint8 xl_info, char *rec)
--- 149,163 ----
  						 xlrec->node.relNode, xlrec->block,
  						 xlrec->latestRemovedXid);
  	}
+ 	if (info == XLOG_HEAP2_FREEZE_PAGE)
+ 	{
+ 		xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) rec;
+ 
+ 		appendStringInfo(buf, "freeze_page: rel %u/%u/%u; blk %u; cutoff xid %u ntuples %u",
+ 						 xlrec->node.spcNode, xlrec->node.dbNode,
+ 						 xlrec->node.relNode, xlrec->block,
+ 						 xlrec->cutoff_xid, xlrec->ntuples);
+ 	}
  	else if (info == XLOG_HEAP2_CLEANUP_INFO)
  	{
  		xl_heap_cleanup_info *xlrec = (xl_heap_cleanup_info *) rec;
*** a/src/backend/access/rmgrdesc/mxactdesc.c
--- b/src/backend/access/rmgrdesc/mxactdesc.c
***************
*** 41,47 **** out_member(StringInfo buf, MultiXactMember *member)
  			appendStringInfoString(buf, "(upd) ");
  			break;
  		default:
! 			appendStringInfoString(buf, "(unk) ");
  			break;
  	}
  }
--- 41,47 ----
  			appendStringInfoString(buf, "(upd) ");
  			break;
  		default:
! 			appendStringInfo(buf, "(unk) ", member->status);
  			break;
  	}
  }
*** a/src/backend/access/transam/multixact.c
--- b/src/backend/access/transam/multixact.c
***************
*** 286,292 **** static MemoryContext MXactContext = NULL;
  
  /* internal MultiXactId management */
  static void MultiXactIdSetOldestVisible(void);
- static MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members);
  static void RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
  				   int nmembers, MultiXactMember *members);
  static MultiXactId GetNewMultiXactId(int nmembers, MultiXactOffset *offset);
--- 286,291 ----
***************
*** 672,678 **** ReadNextMultiXactId(void)
   *
   * NB: the passed members[] array will be sorted in-place.
   */
! static MultiXactId
  CreateMultiXactId(int nmembers, MultiXactMember *members)
  {
  	MultiXactId multi;
--- 671,677 ----
   *
   * NB: the passed members[] array will be sorted in-place.
   */
! MultiXactId
  CreateMultiXactId(int nmembers, MultiXactMember *members)
  {
  	MultiXactId multi;
*** a/src/backend/commands/vacuumlazy.c
--- b/src/backend/commands/vacuumlazy.c
***************
*** 424,429 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 424,430 ----
  	Buffer		vmbuffer = InvalidBuffer;
  	BlockNumber next_not_all_visible_block;
  	bool		skipping_all_visible_blocks;
+ 	xl_heap_freeze_tuple *frozen;
  
  	pg_rusage_init(&ru0);
  
***************
*** 446,451 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 447,453 ----
  	vacrelstats->latestRemovedXid = InvalidTransactionId;
  
  	lazy_space_alloc(vacrelstats, nblocks);
+ 	frozen = palloc(sizeof(xl_heap_freeze_tuple) * MaxHeapTuplesPerPage);
  
  	/*
  	 * We want to skip pages that don't require vacuuming according to the
***************
*** 500,506 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  		bool		tupgone,
  					hastup;
  		int			prev_dead_count;
- 		OffsetNumber frozen[MaxOffsetNumber];
  		int			nfrozen;
  		Size		freespace;
  		bool		all_visible_according_to_vm;
--- 502,507 ----
***************
*** 893,901 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  				 * Each non-removable tuple must be checked to see if it needs
  				 * freezing.  Note we already have exclusive buffer lock.
  				 */
! 				if (heap_freeze_tuple(tuple.t_data, FreezeLimit,
! 									  MultiXactCutoff))
! 					frozen[nfrozen++] = offnum;
  			}
  		}						/* scan along page */
  
--- 894,902 ----
  				 * Each non-removable tuple must be checked to see if it needs
  				 * freezing.  Note we already have exclusive buffer lock.
  				 */
! 				if (heap_prepare_freeze_tuple(tuple.t_data, FreezeLimit,
! 											  MultiXactCutoff, &frozen[nfrozen]))
! 					frozen[nfrozen++].offset = offnum;
  			}
  		}						/* scan along page */
  
***************
*** 906,920 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  		 */
  		if (nfrozen > 0)
  		{
  			MarkBufferDirty(buf);
  			if (RelationNeedsWAL(onerel))
  			{
  				XLogRecPtr	recptr;
  
  				recptr = log_heap_freeze(onerel, buf, FreezeLimit,
! 										 MultiXactCutoff, frozen, nfrozen);
  				PageSetLSN(page, recptr);
  			}
  		}
  
  		/*
--- 907,939 ----
  		 */
  		if (nfrozen > 0)
  		{
+ 			START_CRIT_SECTION();
+ 
  			MarkBufferDirty(buf);
+ 
+ 			/* execute collected freezes */
+ 			for (i = 0; i < nfrozen; i++)
+ 			{
+ 				ItemId		itemid;
+ 				HeapTupleHeader htup;
+ 
+ 				itemid = PageGetItemId(page, frozen[i].offset);
+ 				htup = (HeapTupleHeader) PageGetItem(page, itemid);
+ 
+ 				heap_execute_freeze_tuple(htup, &frozen[i]);
+ 			}
+ 
+ 			/* Now WAL-log freezing if neccessary */
  			if (RelationNeedsWAL(onerel))
  			{
  				XLogRecPtr	recptr;
  
  				recptr = log_heap_freeze(onerel, buf, FreezeLimit,
! 										 frozen, nfrozen);
  				PageSetLSN(page, recptr);
  			}
+ 
+ 			END_CRIT_SECTION();
  		}
  
  		/*
***************
*** 1015,1020 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 1034,1041 ----
  			RecordPageWithFreeSpace(onerel, blkno, freespace);
  	}
  
+ 	pfree(frozen);
+ 
  	/* save stats for use later */
  	vacrelstats->scanned_tuples = num_tuples;
  	vacrelstats->tuples_deleted = tups_vacuumed;
*** a/src/include/access/heapam_xlog.h
--- b/src/include/access/heapam_xlog.h
***************
*** 50,56 ****
   */
  #define XLOG_HEAP2_FREEZE		0x00
  #define XLOG_HEAP2_CLEAN		0x10
! /* 0x20 is free, was XLOG_HEAP2_CLEAN_MOVE */
  #define XLOG_HEAP2_CLEANUP_INFO 0x30
  #define XLOG_HEAP2_VISIBLE		0x40
  #define XLOG_HEAP2_MULTI_INSERT 0x50
--- 50,56 ----
   */
  #define XLOG_HEAP2_FREEZE		0x00
  #define XLOG_HEAP2_CLEAN		0x10
! #define XLOG_HEAP2_FREEZE_PAGE	0x20
  #define XLOG_HEAP2_CLEANUP_INFO 0x30
  #define XLOG_HEAP2_VISIBLE		0x40
  #define XLOG_HEAP2_MULTI_INSERT 0x50
***************
*** 239,245 **** typedef struct xl_heap_inplace
  
  #define SizeOfHeapInplace	(offsetof(xl_heap_inplace, target) + SizeOfHeapTid)
  
! /* This is what we need to know about tuple freezing during vacuum */
  typedef struct xl_heap_freeze
  {
  	RelFileNode node;
--- 239,245 ----
  
  #define SizeOfHeapInplace	(offsetof(xl_heap_inplace, target) + SizeOfHeapTid)
  
! /* This is what we need to know about tuple freezing during vacuum (legacy) */
  typedef struct xl_heap_freeze
  {
  	RelFileNode node;
***************
*** 251,256 **** typedef struct xl_heap_freeze
--- 251,289 ----
  
  #define SizeOfHeapFreeze (offsetof(xl_heap_freeze, cutoff_multi) + sizeof(MultiXactId))
  
+ /*
+  * a 'freeze plan' struct that represents what we need to know about a single
+  * tuple being frozen during vacuum
+  */
+ #define		XLH_FREEZE_XMIN		0x01
+ #define		XLH_FREEZE_XVAC		0x02
+ #define		XLH_INVALID_XVAC	0x04
+ 
+ typedef struct xl_heap_freeze_tuple
+ {
+ 	TransactionId xmax;
+ 	OffsetNumber offset;
+ 	uint16		t_infomask2;
+ 	uint16		t_infomask;
+ 	uint8		frzflags;
+ } xl_heap_freeze_tuple;
+ 
+ /* XXX we could define size as offsetof(struct, frzflags) and save some
+  * padding, but then the array below wouldn't work properly ... */
+ #define SizeOfHeapFreezeTuple sizeof(xl_heap_freeze_tuple)
+ 
+ /*
+  * This is what we need to know about a block being frozen during vacuum
+  */
+ typedef struct xl_heap_freeze_block
+ {
+ 	RelFileNode node;
+ 	BlockNumber block;
+ 	TransactionId cutoff_xid;
+ 	uint16		ntuples;
+ 	xl_heap_freeze_tuple tuples[FLEXIBLE_ARRAY_MEMBER];
+ } xl_heap_freeze_page;
+ 
  /* This is what we need to know about setting a visibility map bit */
  typedef struct xl_heap_visible
  {
***************
*** 277,284 **** extern XLogRecPtr log_heap_clean(Relation reln, Buffer buffer,
  			   OffsetNumber *nowunused, int nunused,
  			   TransactionId latestRemovedXid);
  extern XLogRecPtr log_heap_freeze(Relation reln, Buffer buffer,
! 				TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				OffsetNumber *offsets, int offcnt);
  extern XLogRecPtr log_heap_visible(RelFileNode rnode, Buffer heap_buffer,
  				 Buffer vm_buffer, TransactionId cutoff_xid);
  extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
--- 310,321 ----
  			   OffsetNumber *nowunused, int nunused,
  			   TransactionId latestRemovedXid);
  extern XLogRecPtr log_heap_freeze(Relation reln, Buffer buffer,
! 		  TransactionId cutoff_xid,	xl_heap_freeze_tuple *tuples, int ntuples);
! extern bool heap_prepare_freeze_tuple(HeapTupleHeader tuple,
! 						  TransactionId cutoff_xid, TransactionId cutoff_multi,
! 						  xl_heap_freeze_tuple *frz);
! extern void heap_execute_freeze_tuple(HeapTupleHeader tuple,
! 						  xl_heap_freeze_tuple *xlrec_tp);
  extern XLogRecPtr log_heap_visible(RelFileNode rnode, Buffer heap_buffer,
  				 Buffer vm_buffer, TransactionId cutoff_xid);
  extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
*** a/src/include/access/multixact.h
--- b/src/include/access/multixact.h
***************
*** 81,86 **** extern MultiXactId MultiXactIdCreate(TransactionId xid1,
--- 81,87 ----
  				  MultiXactStatus status2);
  extern MultiXactId MultiXactIdExpand(MultiXactId multi, TransactionId xid,
  				  MultiXactStatus status);
+ extern MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members);
  extern MultiXactId ReadNextMultiXactId(void);
  extern bool MultiXactIdIsRunning(MultiXactId multi);
  extern void MultiXactIdSetOldestMember(void);

*** a/src/backend/access/heap/heapam.c
--- b/src/backend/access/heap/heapam.c
***************
*** 5238,5251 **** heap_inplace_update(Relation relation, HeapTuple tuple)
  		CacheInvalidateHeapTuple(relation, tuple, NULL);
  }
  
  
  /*
!  * heap_freeze_tuple
   *
   * Check to see whether any of the XID fields of a tuple (xmin, xmax, xvac)
!  * are older than the specified cutoff XID.  If so, replace them with
!  * FrozenTransactionId or InvalidTransactionId as appropriate, and return
!  * TRUE.  Return FALSE if nothing was changed.
   *
   * It is assumed that the caller has checked the tuple with
   * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
--- 5238,5498 ----
  		CacheInvalidateHeapTuple(relation, tuple, NULL);
  }
  
+ #define		FRM_NOOP				0x0001
+ #define		FRM_INVALIDATE_XMAX		0x0002
+ #define		FRM_RETURN_IS_XID		0x0004
+ #define		FRM_RETURN_IS_MULTI		0x0008
+ #define		FRM_MARK_COMMITTED		0x0010
  
  /*
!  * FreezeMultiXactId
!  *		Determine what to do during freezing when a tuple is marked by a
!  *		MultiXactId.
!  *
!  * NB -- this might have the side-effect of creating a new MultiXactId!
!  *
!  * "flags" is an output value; it's used to tell caller what to do on return.
!  * Possible flags are:
!  * FRM_NOOP
!  *		don't do anything -- keep existing Xmax
!  * FRM_INVALIDATE_XMAX
!  *		mark Xmax as InvalidTransactionId and set XMAX_INVALID flag.
!  * FRM_RETURN_IS_XID
!  *		The Xid return value is a single update Xid to set as xmax.
!  * FRM_MARK_COMMITTED
!  *		Xmax can be marked as HEAP_XMAX_COMMITTED
!  * FRM_RETURN_IS_MULTI
!  *		The return value is a new MultiXactId to set as new Xmax.
!  *		(caller must obtain proper infomask bits using GetMultiXactIdHintBits)
!  */
! static TransactionId
! FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
! 				  TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				  uint16 *flags)
! {
! 	TransactionId xid = InvalidTransactionId;
! 	int			i;
! 	MultiXactMember *members;
! 	int			nmembers;
! 	bool		need_replace;
! 	int			nnewmembers;
! 	MultiXactMember *newmembers;
! 	bool		has_lockers;
! 	TransactionId update_xid;
! 	bool		update_committed;
! 
! 	*flags = 0;
! 
! 	/* We should only be called in Multis */
! 	Assert(t_infomask & HEAP_XMAX_IS_MULTI);
! 
! 	if (!MultiXactIdIsValid(multi))
! 	{
! 		/* Ensure infomask bits are appropriately set/reset */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		return InvalidTransactionId;
! 	}
! 	else if (MultiXactIdPrecedes(multi, cutoff_multi))
! 	{
! 		/*
! 		 * This old multi cannot possibly have members still running.  If it
! 		 * was a locker only, it can be removed without any further
! 		 * consideration; but if it contained an update, we might need to
! 		 * preserve it.
! 		 */
! 		Assert(!MultiXactIdIsRunning(multi));
! 		if (HEAP_XMAX_IS_LOCKED_ONLY(t_infomask))
! 		{
! 			*flags |= FRM_INVALIDATE_XMAX;
! 			xid = InvalidTransactionId; /* not strictly necessary */
! 		}
! 		else
! 		{
! 			/* replace multi by update xid */
! 			xid = MultiXactIdGetUpdateXid(multi, t_infomask);
! 
! 			/* wasn't only a lock, xid needs to be valid */
! 			Assert(TransactionIdIsValid(xid));
! 
! 			/*
! 			 * If the xid is older than the cutoff, it has to have aborted,
! 			 * otherwise the tuple would have gotten pruned away.
! 			 */
! 			if (TransactionIdPrecedes(xid, cutoff_xid))
! 			{
! 				Assert(!TransactionIdDidCommit(xid));
! 				*flags |= FRM_INVALIDATE_XMAX;
! 				xid = InvalidTransactionId;		/* not strictly necessary */
! 			}
! 			else
! 				*flags |= FRM_RETURN_IS_XID;
! 		}
! 
! 		return xid;
! 	}
! 
! 	/*
! 	 * This multixact might have or might not have members still running, but
! 	 * we know it's valid and is newer than the cutoff point for multis.
! 	 * However, some member(s) of it may be below the cutoff for Xids, so we
! 	 * need to walk the whole members array to figure out what to do, if
! 	 * anything.
! 	 */
! 
! 	nmembers = GetMultiXactIdMembers(multi, &members, false);
! 	if (nmembers <= 0)
! 	{
! 		/* Nothing worth keeping */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		return InvalidTransactionId;
! 	}
! 
! 	/* is there anything older than the cutoff? */
! 	need_replace = false;
! 	for (i = 0; i < nmembers; i++)
! 	{
! 		if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
! 		{
! 			need_replace = true;
! 			break;
! 		}
! 	}
! 
! 	/*
! 	 * In the simplest case, there is no member older than the cutoff; we can
! 	 * keep the existing MultiXactId as is.
! 	 */
! 	if (!need_replace)
! 	{
! 		*flags |= FRM_NOOP;
! 		pfree(members);
! 		return InvalidTransactionId;
! 	}
! 
! 	/*
! 	 * If the multi needs to be updated, figure out which members do we need
! 	 * to keep.
! 	 */
! 	nnewmembers = 0;
! 	newmembers = palloc(sizeof(MultiXactMember) * nmembers);
! 	has_lockers = false;
! 	update_xid = InvalidTransactionId;
! 	update_committed = false;
! 
! 	for (i = 0; i < nmembers; i++)
! 	{
! 		if (ISUPDATE_from_mxstatus(members[i].status))
! 		{
! 			/*
! 			 * It's an update; should we keep it?  If the transaction is known
! 			 * aborted then it's okay to ignore it, otherwise not.  (Note this
! 			 * is just an optimization and not needed for correctness, so it's
! 			 * okay to get this test wrong; for example, in case an updater is
! 			 * crashed, or a running transaction in the process of aborting.)
! 			 */
! 			if (!TransactionIdDidAbort(members[i].xid))
! 			{
! 				newmembers[nnewmembers++] = members[i];
! 				Assert(!TransactionIdIsValid(update_xid));
! 
! 				/*
! 				 * Tell caller to set HEAP_XMAX_COMMITTED hint while we have
! 				 * the Xid in cache.  Again, this is just an optimization, so
! 				 * it's not a problem if the transaction is still running and
! 				 * in the process of committing.
! 				 */
! 				if (TransactionIdDidCommit(update_xid))
! 					update_committed = true;
! 
! 				update_xid = newmembers[i].xid;
! 			}
! 
! 			/*
! 			 * Checking for very old update Xids is critical: if the update
! 			 * member of the multi is older than cutoff_xid, we must remove
! 			 * it, because otherwise a later liveliness check could attempt
! 			 * pg_clog access for a page that was truncated away by the
! 			 * current vacuum.	Note that if the update had committed, we
! 			 * wouldn't be freezing this tuple because it would have gotten
! 			 * removed (HEAPTUPLE_DEAD) by HeapTupleSatisfiesVacuum; so it
! 			 * either aborted or crashed.  Therefore, ignore this update_xid.
! 			 */
! 			if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 			{
! 				update_xid = InvalidTransactionId;
! 				update_committed = false;
! 
! 			}
! 		}
! 		else
! 		{
! 			/* We only keep lockers if they are still running */
! 			if (TransactionIdIsCurrentTransactionId(members[i].xid) ||
! 				TransactionIdIsInProgress(members[i].xid))
! 			{
! 				/* running locker cannot possibly be older than the cutoff */
! 				Assert(!TransactionIdPrecedes(members[i].xid, cutoff_xid));
! 				newmembers[nnewmembers++] = members[i];
! 				has_lockers = true;
! 			}
! 		}
! 	}
! 
! 	pfree(members);
! 
! 	if (nnewmembers == 0)
! 	{
! 		/* nothing worth keeping!? Tell caller to remove the whole thing */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		xid = InvalidTransactionId;
! 	}
! 	else if (TransactionIdIsValid(update_xid) && !has_lockers)
! 	{
! 		/*
! 		 * If there's a single member and it's an update, pass it back alone
! 		 * without creating a new Multi.  (XXX we could do this when there's a
! 		 * single remaining locker, too, but that would complicate the API too
! 		 * much; moreover, the case with the single updater is more
! 		 * interesting, because those are longer-lived.)
! 		 */
! 		Assert(nnewmembers == 1);
! 		*flags |= FRM_RETURN_IS_XID;
! 		if (update_committed)
! 			*flags |= FRM_MARK_COMMITTED;
! 		xid = update_xid;
! 	}
! 	else
! 	{
! 		/*
! 		 * Create a new multixact with the surviving members of the previous
! 		 * one, to set as new Xmax in the tuple.
! 		 *
! 		 * If this is the first possibly-multixact-able operation in the
! 		 * current transaction, set my per-backend OldestMemberMXactId
! 		 * setting. We can be certain that the transaction will never become a
! 		 * member of any older MultiXactIds than that.
! 		 */
! 		MultiXactIdSetOldestMember();
! 		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers);
! 		*flags |= FRM_RETURN_IS_MULTI;
! 	}
! 
! 	pfree(newmembers);
! 
! 	return xid;
! }
! 
! /*
!  * heap_prepare_freeze_tuple
   *
   * Check to see whether any of the XID fields of a tuple (xmin, xmax, xvac)
!  * are older than the specified cutoff XID and cutoff MultiXactId.	If so,
!  * setup enough state (in the *frz output argument) to later execute and
!  * WAL-log what we would need to do, and return TRUE.  Return FALSE if nothing
!  * is to be changed.
!  *
!  * Caller is responsible for setting the offset field, if appropriate.	This
!  * is only necessary if the freeze is to be WAL-logged.
   *
   * It is assumed that the caller has checked the tuple with
   * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
***************
*** 5254,5307 **** heap_inplace_update(Relation relation, HeapTuple tuple)
   * NB: cutoff_xid *must* be <= the current global xmin, to ensure that any
   * XID older than it could neither be running nor seen as running by any
   * open transaction.  This ensures that the replacement will not change
!  * anyone's idea of the tuple state.  Also, since we assume the tuple is
!  * not HEAPTUPLE_DEAD, the fact that an XID is not still running allows us
!  * to assume that it is either committed good or aborted, as appropriate;
!  * so we need no external state checks to decide what to do.  (This is good
!  * because this function is applied during WAL recovery, when we don't have
!  * access to any such state, and can't depend on the hint bits to be set.)
!  * There is an exception we make which is to assume GetMultiXactIdMembers can
!  * be called during recovery.
!  *
   * Similarly, cutoff_multi must be less than or equal to the smallest
   * MultiXactId used by any transaction currently open.
   *
   * If the tuple is in a shared buffer, caller must hold an exclusive lock on
   * that buffer.
   *
!  * Note: it might seem we could make the changes without exclusive lock, since
!  * TransactionId read/write is assumed atomic anyway.  However there is a race
!  * condition: someone who just fetched an old XID that we overwrite here could
!  * conceivably not finish checking the XID against pg_clog before we finish
!  * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
!  * exclusive lock ensures no other backend is in process of checking the
!  * tuple status.  Also, getting exclusive lock makes it safe to adjust the
!  * infomask bits.
!  *
!  * NB: Cannot rely on hint bits here, they might not be set after a crash or
!  * on a standby.
   */
  bool
! heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
! 				  MultiXactId cutoff_multi)
  {
  	bool		changed = false;
  	bool		freeze_xmax = false;
  	TransactionId xid;
  
  	/* Process xmin */
  	xid = HeapTupleHeaderGetXmin(tuple);
  	if (TransactionIdIsNormal(xid) &&
  		TransactionIdPrecedes(xid, cutoff_xid))
  	{
! 		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
  
  		/*
  		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
  		 * already be set here, but there's a small chance not.
  		 */
! 		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
  		changed = true;
  	}
  
--- 5501,5544 ----
   * NB: cutoff_xid *must* be <= the current global xmin, to ensure that any
   * XID older than it could neither be running nor seen as running by any
   * open transaction.  This ensures that the replacement will not change
!  * anyone's idea of the tuple state.
   * Similarly, cutoff_multi must be less than or equal to the smallest
   * MultiXactId used by any transaction currently open.
   *
   * If the tuple is in a shared buffer, caller must hold an exclusive lock on
   * that buffer.
   *
!  * NB: It is not enough to set hint bits to indicate something is
!  * committed/invalid -- they might not be set on a standby, or after crash
!  * recovery.  We really need to remove old xids.
   */
  bool
! heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
! 						  TransactionId cutoff_multi,
! 						  xl_heap_freeze_tuple *frz)
! 
  {
  	bool		changed = false;
  	bool		freeze_xmax = false;
  	TransactionId xid;
  
+ 	frz->frzflags = 0;
+ 	frz->t_infomask2 = tuple->t_infomask2;
+ 	frz->t_infomask = tuple->t_infomask;
+ 	frz->xmax = HeapTupleHeaderGetRawXmax(tuple);
+ 
  	/* Process xmin */
  	xid = HeapTupleHeaderGetXmin(tuple);
  	if (TransactionIdIsNormal(xid) &&
  		TransactionIdPrecedes(xid, cutoff_xid))
  	{
! 		frz->frzflags |= XLH_FREEZE_XMIN;
  
  		/*
  		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
  		 * already be set here, but there's a small chance not.
  		 */
! 		frz->t_infomask |= HEAP_XMIN_COMMITTED;
  		changed = true;
  	}
  
***************
*** 5318,5408 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  
  	if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
  	{
! 		if (!MultiXactIdIsValid(xid))
! 		{
! 			/* no xmax set, ignore */
! 			;
! 		}
! 		else if (MultiXactIdPrecedes(xid, cutoff_multi))
! 		{
! 			/*
! 			 * This old multi cannot possibly be running.  If it was a locker
! 			 * only, it can be removed without much further thought; but if it
! 			 * contained an update, we need to preserve it.
! 			 */
! 			if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
! 				freeze_xmax = true;
! 			else
! 			{
! 				TransactionId update_xid;
  
! 				update_xid = HeapTupleGetUpdateXid(tuple);
! 
! 				/*
! 				 * The multixact has an update hidden within.  Get rid of it.
! 				 *
! 				 * If the update_xid is below the cutoff_xid, it necessarily
! 				 * must be an aborted transaction.  In a primary server, such
! 				 * an Xmax would have gotten marked invalid by
! 				 * HeapTupleSatisfiesVacuum, but in a replica that is not
! 				 * called before we are, so deal with it in the same way.
! 				 *
! 				 * If not below the cutoff_xid, then the tuple would have been
! 				 * pruned by vacuum, if the update committed long enough ago,
! 				 * and we wouldn't be freezing it; so it's either recently
! 				 * committed, or in-progress.  Deal with this by setting the
! 				 * Xmax to the update Xid directly and remove the IS_MULTI
! 				 * bit.  (We know there cannot be running lockers in this
! 				 * multi, because it's below the cutoff_multi value.)
! 				 */
  
! 				if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 				{
! 					Assert(InRecovery || TransactionIdDidAbort(update_xid));
! 					freeze_xmax = true;
! 				}
! 				else
! 				{
! 					Assert(InRecovery || !TransactionIdIsInProgress(update_xid));
! 					tuple->t_infomask &= ~HEAP_XMAX_BITS;
! 					HeapTupleHeaderSetXmax(tuple, update_xid);
! 					changed = true;
! 				}
! 			}
  		}
! 		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
  		{
! 			/* newer than the cutoff, so don't touch it */
! 			;
  		}
  		else
  		{
! 			TransactionId	update_xid;
! 
! 			/*
! 			 * This is a multixact which is not marked LOCK_ONLY, but which
! 			 * is newer than the cutoff_multi.  If the update_xid is below the
! 			 * cutoff_xid point, then we can just freeze the Xmax in the
! 			 * tuple, removing it altogether.  This seems simple, but there
! 			 * are several underlying assumptions:
! 			 *
! 			 * 1. A tuple marked by an multixact containing a very old
! 			 * committed update Xid would have been pruned away by vacuum; we
! 			 * wouldn't be freezing this tuple at all.
! 			 *
! 			 * 2. There cannot possibly be any live locking members remaining
! 			 * in the multixact.  This is because if they were alive, the
! 			 * update's Xid would had been considered, via the lockers'
! 			 * snapshot's Xmin, as part the cutoff_xid.
! 			 *
! 			 * 3. We don't create new MultiXacts via MultiXactIdExpand() that
! 			 * include a very old aborted update Xid: in that function we only
! 			 * include update Xids corresponding to transactions that are
! 			 * committed or in-progress.
! 			 */
! 			update_xid = HeapTupleGetUpdateXid(tuple);
! 			if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 				freeze_xmax = true;
  		}
  	}
  	else if (TransactionIdIsNormal(xid) &&
--- 5555,5589 ----
  
  	if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
  	{
! 		TransactionId newxmax;
! 		uint16		flags;
  
! 		newxmax = FreezeMultiXactId(xid, tuple->t_infomask,
! 									cutoff_xid, cutoff_multi, &flags);
  
! 		if (flags & FRM_INVALIDATE_XMAX)
! 			freeze_xmax = true;
! 		else if (flags & FRM_RETURN_IS_XID)
! 		{
! 			frz->t_infomask &= ~HEAP_XMAX_BITS;
! 			frz->xmax = newxmax;
! 			if (flags & FRM_MARK_COMMITTED)
! 				frz->t_infomask &= HEAP_XMAX_COMMITTED;
! 			changed = true;
  		}
! 		else if (flags & FRM_RETURN_IS_MULTI)
  		{
! 			frz->t_infomask &= ~HEAP_XMAX_BITS;
! 			frz->xmax = newxmax;
! 
! 			GetMultiXactIdHintBits(newxmax,
! 								   &frz->t_infomask,
! 								   &frz->t_infomask2);
! 			changed = true;
  		}
  		else
  		{
! 			Assert(flags & FRM_NOOP);
  		}
  	}
  	else if (TransactionIdIsNormal(xid) &&
***************
*** 5413,5429 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  
  	if (freeze_xmax)
  	{
! 		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
  
  		/*
  		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
  		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
  		 * Also get rid of the HEAP_KEYS_UPDATED bit.
  		 */
! 		tuple->t_infomask &= ~HEAP_XMAX_BITS;
! 		tuple->t_infomask |= HEAP_XMAX_INVALID;
! 		HeapTupleHeaderClearHotUpdated(tuple);
! 		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
  		changed = true;
  	}
  
--- 5594,5610 ----
  
  	if (freeze_xmax)
  	{
! 		frz->xmax = InvalidTransactionId;
  
  		/*
  		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
  		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
  		 * Also get rid of the HEAP_KEYS_UPDATED bit.
  		 */
! 		frz->t_infomask &= ~HEAP_XMAX_BITS;
! 		frz->t_infomask |= HEAP_XMAX_INVALID;
! 		frz->t_infomask2 &= ~HEAP_HOT_UPDATED;
! 		frz->t_infomask2 &= ~HEAP_KEYS_UPDATED;
  		changed = true;
  	}
  
***************
*** 5443,5458 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  			 * xvac transaction succeeded.
  			 */
  			if (tuple->t_infomask & HEAP_MOVED_OFF)
! 				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
  			else
! 				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
  
  			/*
  			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
  			 * will already be set here, but there's a small chance not.
  			 */
  			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
  			changed = true;
  		}
  	}
--- 5624,5639 ----
  			 * xvac transaction succeeded.
  			 */
  			if (tuple->t_infomask & HEAP_MOVED_OFF)
! 				frz->frzflags |= XLH_INVALID_XVAC;
  			else
! 				frz->frzflags |= XLH_FREEZE_XVAC;
  
  			/*
  			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
  			 * will already be set here, but there's a small chance not.
  			 */
  			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 			frz->t_infomask |= HEAP_XMIN_COMMITTED;
  			changed = true;
  		}
  	}
***************
*** 5461,5466 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
--- 5642,5709 ----
  }
  
  /*
+  * heap_execute_freeze_tuple
+  *		Execute the prepared freezing of a tuple.
+  *
+  * Caller is responsible for ensuring that no other backend can access the
+  * storage underlying this tuple, either by holding an exclusive lock on the
+  * buffer containing it (which is what lazy VACUUM does), or by having it by
+  * in private storage (which is what CLUSTER and friends do).
+  *
+  * Note: it might seem we could make the changes without exclusive lock, since
+  * TransactionId read/write is assumed atomic anyway.  However there is a race
+  * condition: someone who just fetched an old XID that we overwrite here could
+  * conceivably not finish checking the XID against pg_clog before we finish
+  * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
+  * exclusive lock ensures no other backend is in process of checking the
+  * tuple status.  Also, getting exclusive lock makes it safe to adjust the
+  * infomask bits.
+  *
+  * NB: All code in here must be safe to execute during crash recovery!
+  */
+ void
+ heap_execute_freeze_tuple(HeapTupleHeader tuple, xl_heap_freeze_tuple *frz)
+ {
+ 	if (frz->frzflags & XLH_FREEZE_XMIN)
+ 		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+ 
+ 	HeapTupleHeaderSetXmax(tuple, frz->xmax);
+ 
+ 	if (frz->frzflags & XLH_FREEZE_XVAC)
+ 		HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+ 
+ 	if (frz->frzflags & XLH_INVALID_XVAC)
+ 		HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+ 
+ 	tuple->t_infomask = frz->t_infomask;
+ 	tuple->t_infomask2 = frz->t_infomask2;
+ }
+ 
+ /*
+  * heap_freeze_tuple - freeze tuple inplace without WAL logging.
+  *
+  * Useful for callers like CLUSTER that perform their own WAL logging.
+  */
+ bool
+ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+ 				  TransactionId cutoff_multi)
+ {
+ 	xl_heap_freeze_tuple frz;
+ 	bool		do_freeze;
+ 
+ 	do_freeze = heap_prepare_freeze_tuple(tuple, cutoff_xid, cutoff_multi, &frz);
+ 
+ 	/*
+ 	 * Note that because this is not a WAL-logged operation, we don't need to
+ 	 * fill in the offset in the freeze record.
+ 	 */
+ 
+ 	if (do_freeze)
+ 		heap_execute_freeze_tuple(tuple, &frz);
+ 	return do_freeze;
+ }
+ 
+ /*
   * For a given MultiXactId, return the hint bits that should be set in the
   * tuple's infomask.
   *
***************
*** 5763,5778 **** heap_tuple_needs_freeze(HeapTupleHeader tuple, TransactionId cutoff_xid,
  		}
  		else if (MultiXactIdPrecedes(multi, cutoff_multi))
  			return true;
- 		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
- 		{
- 			/* only-locker multis don't need internal examination */
- 			;
- 		}
  		else
  		{
! 			if (TransactionIdPrecedes(HeapTupleGetUpdateXid(tuple),
! 									  cutoff_xid))
! 				return true;
  		}
  	}
  	else
--- 6006,6031 ----
  		}
  		else if (MultiXactIdPrecedes(multi, cutoff_multi))
  			return true;
  		else
  		{
! 			MultiXactMember *members;
! 			int			nmembers;
! 			int			i;
! 
! 			/* need to check whether any member of the mxact is too old */
! 
! 			nmembers = GetMultiXactIdMembers(multi, &members, false);
! 
! 			for (i = 0; i < nmembers; i++)
! 			{
! 				if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
! 				{
! 					pfree(members);
! 					return true;
! 				}
! 			}
! 			if (nmembers > 0)
! 				pfree(members);
  		}
  	}
  	else
***************
*** 6022,6066 **** log_heap_clean(Relation reln, Buffer buffer,
  }
  
  /*
!  * Perform XLogInsert for a heap-freeze operation.	Caller must already
!  * have modified the buffer and marked it dirty.
   */
  XLogRecPtr
! log_heap_freeze(Relation reln, Buffer buffer,
! 				TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				OffsetNumber *offsets, int offcnt)
  {
! 	xl_heap_freeze xlrec;
  	XLogRecPtr	recptr;
  	XLogRecData rdata[2];
  
  	/* Caller should not call me on a non-WAL-logged relation */
  	Assert(RelationNeedsWAL(reln));
  	/* nor when there are no tuples to freeze */
! 	Assert(offcnt > 0);
  
  	xlrec.node = reln->rd_node;
  	xlrec.block = BufferGetBlockNumber(buffer);
  	xlrec.cutoff_xid = cutoff_xid;
! 	xlrec.cutoff_multi = cutoff_multi;
  
  	rdata[0].data = (char *) &xlrec;
! 	rdata[0].len = SizeOfHeapFreeze;
  	rdata[0].buffer = InvalidBuffer;
  	rdata[0].next = &(rdata[1]);
  
  	/*
! 	 * The tuple-offsets array is not actually in the buffer, but pretend that
! 	 * it is.  When XLogInsert stores the whole buffer, the offsets array need
  	 * not be stored too.
  	 */
! 	rdata[1].data = (char *) offsets;
! 	rdata[1].len = offcnt * sizeof(OffsetNumber);
  	rdata[1].buffer = buffer;
  	rdata[1].buffer_std = true;
  	rdata[1].next = NULL;
  
! 	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE, rdata);
  
  	return recptr;
  }
--- 6275,6318 ----
  }
  
  /*
!  * Perform XLogInsert for a heap-freeze operation.	Caller must have already
!  * modified the buffer and marked it dirty.
   */
  XLogRecPtr
! log_heap_freeze(Relation reln, Buffer buffer, TransactionId cutoff_xid,
! 				xl_heap_freeze_tuple *tuples, int ntuples)
  {
! 	xl_heap_freeze_page xlrec;
  	XLogRecPtr	recptr;
  	XLogRecData rdata[2];
  
  	/* Caller should not call me on a non-WAL-logged relation */
  	Assert(RelationNeedsWAL(reln));
  	/* nor when there are no tuples to freeze */
! 	Assert(ntuples > 0);
  
  	xlrec.node = reln->rd_node;
  	xlrec.block = BufferGetBlockNumber(buffer);
  	xlrec.cutoff_xid = cutoff_xid;
! 	xlrec.ntuples = ntuples;
  
  	rdata[0].data = (char *) &xlrec;
! 	rdata[0].len = SizeOfHeapFreezePage;
  	rdata[0].buffer = InvalidBuffer;
  	rdata[0].next = &(rdata[1]);
  
  	/*
! 	 * The freeze plan array is not actually in the buffer, but pretend that
! 	 * it is.  When XLogInsert stores the whole buffer, the freeze plan need
  	 * not be stored too.
  	 */
! 	rdata[1].data = (char *) tuples;
! 	rdata[1].len = ntuples * sizeof(xl_heap_freeze_tuple);
  	rdata[1].buffer = buffer;
  	rdata[1].buffer_std = true;
  	rdata[1].next = NULL;
  
! 	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE_PAGE, rdata);
  
  	return recptr;
  }
***************
*** 6402,6407 **** heap_xlog_clean(XLogRecPtr lsn, XLogRecord *record)
--- 6654,6752 ----
  	XLogRecordPageWithFreeSpace(xlrec->node, xlrec->block, freespace);
  }
  
+ /*
+  * Freeze a single tuple for XLOG_HEAP2_FREEZE
+  *
+  * NB: This type of record aren't generated anymore, since bugs around
+  * multixacts couldn't be fixed without a more robust type of freezing. This
+  * is kept around to be able to perform PITR.
+  */
+ static bool
+ heap_xlog_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+ 					   MultiXactId cutoff_multi)
+ {
+ 	bool		changed = false;
+ 	TransactionId xid;
+ 
+ 	xid = HeapTupleHeaderGetXmin(tuple);
+ 	if (TransactionIdIsNormal(xid) &&
+ 		TransactionIdPrecedes(xid, cutoff_xid))
+ 	{
+ 		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+ 
+ 		/*
+ 		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
+ 		 * already be set here, but there's a small chance not.
+ 		 */
+ 		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
+ 		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+ 		changed = true;
+ 	}
+ 
+ 	/*
+ 	 * Note that this code handles IS_MULTI Xmax values, too, but only to mark
+ 	 * the tuple as not updated if the multixact is below the cutoff Multixact
+ 	 * given; it doesn't remove dead members of a very old multixact.
+ 	 */
+ 	xid = HeapTupleHeaderGetRawXmax(tuple);
+ 	if ((tuple->t_infomask & HEAP_XMAX_IS_MULTI) ?
+ 		(MultiXactIdIsValid(xid) &&
+ 		 MultiXactIdPrecedes(xid, cutoff_multi)) :
+ 		(TransactionIdIsNormal(xid) &&
+ 		 TransactionIdPrecedes(xid, cutoff_xid)))
+ 	{
+ 		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
+ 
+ 		/*
+ 		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
+ 		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
+ 		 * Also get rid of the HEAP_KEYS_UPDATED bit.
+ 		 */
+ 		tuple->t_infomask &= ~HEAP_XMAX_BITS;
+ 		tuple->t_infomask |= HEAP_XMAX_INVALID;
+ 		HeapTupleHeaderClearHotUpdated(tuple);
+ 		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
+ 		changed = true;
+ 	}
+ 
+ 	/*
+ 	 * Old-style VACUUM FULL is gone, but we have to keep this code as long as
+ 	 * we support having MOVED_OFF/MOVED_IN tuples in the database.
+ 	 */
+ 	if (tuple->t_infomask & HEAP_MOVED)
+ 	{
+ 		xid = HeapTupleHeaderGetXvac(tuple);
+ 		if (TransactionIdIsNormal(xid) &&
+ 			TransactionIdPrecedes(xid, cutoff_xid))
+ 		{
+ 			/*
+ 			 * If a MOVED_OFF tuple is not dead, the xvac transaction must
+ 			 * have failed; whereas a non-dead MOVED_IN tuple must mean the
+ 			 * xvac transaction succeeded.
+ 			 */
+ 			if (tuple->t_infomask & HEAP_MOVED_OFF)
+ 				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+ 			else
+ 				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+ 
+ 			/*
+ 			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
+ 			 * will already be set here, but there's a small chance not.
+ 			 */
+ 			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
+ 			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+ 			changed = true;
+ 		}
+ 	}
+ 
+ 	return changed;
+ }
+ 
+ /*
+  * NB: This type of record aren't generated anymore, since bugs around
+  * multixacts couldn't be fixed without a more robust type of freezing. This
+  * is kept around to be able to perform PITR.
+  */
  static void
  heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
  {
***************
*** 6450,6456 **** heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
  			ItemId		lp = PageGetItemId(page, *offsets);
  			HeapTupleHeader tuple = (HeapTupleHeader) PageGetItem(page, lp);
  
! 			(void) heap_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
  			offsets++;
  		}
  	}
--- 6795,6801 ----
  			ItemId		lp = PageGetItemId(page, *offsets);
  			HeapTupleHeader tuple = (HeapTupleHeader) PageGetItem(page, lp);
  
! 			(void) heap_xlog_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
  			offsets++;
  		}
  	}
***************
*** 6574,6579 **** heap_xlog_visible(XLogRecPtr lsn, XLogRecord *record)
--- 6919,6981 ----
  	}
  }
  
+ /*
+  * Replay XLOG_HEAP2_FREEZE_PAGE records
+  */
+ static void
+ heap_xlog_freeze_page(XLogRecPtr lsn, XLogRecord *record)
+ {
+ 	xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) XLogRecGetData(record);
+ 	TransactionId cutoff_xid = xlrec->cutoff_xid;
+ 	Buffer		buffer;
+ 	Page		page;
+ 	int			ntup;
+ 
+ 	/*
+ 	 * In Hot Standby mode, ensure that there's no queries running which still
+ 	 * consider the frozen xids as running.
+ 	 */
+ 	if (InHotStandby)
+ 		ResolveRecoveryConflictWithSnapshot(cutoff_xid, xlrec->node);
+ 
+ 	/* If we have a full-page image, restore it and we're done */
+ 	if (record->xl_info & XLR_BKP_BLOCK(0))
+ 	{
+ 		(void) RestoreBackupBlock(lsn, record, 0, false, false);
+ 		return;
+ 	}
+ 
+ 	buffer = XLogReadBuffer(xlrec->node, xlrec->block, false);
+ 	if (!BufferIsValid(buffer))
+ 		return;
+ 
+ 	page = (Page) BufferGetPage(buffer);
+ 
+ 	if (lsn <= PageGetLSN(page))
+ 	{
+ 		UnlockReleaseBuffer(buffer);
+ 		return;
+ 	}
+ 
+ 	/* now execute freeze plan for each frozen tuple */
+ 	for (ntup = 0; ntup < xlrec->ntuples; ntup++)
+ 	{
+ 		xl_heap_freeze_tuple *xlrec_tp;
+ 		ItemId		lp;
+ 		HeapTupleHeader tuple;
+ 
+ 		xlrec_tp = &xlrec->tuples[ntup];
+ 		lp = PageGetItemId(page, xlrec_tp->offset);		/* offsets are one-based */
+ 		tuple = (HeapTupleHeader) PageGetItem(page, lp);
+ 
+ 		heap_execute_freeze_tuple(tuple, xlrec_tp);
+ 	}
+ 
+ 	PageSetLSN(page, lsn);
+ 	MarkBufferDirty(buffer);
+ 	UnlockReleaseBuffer(buffer);
+ }
+ 
  static void
  heap_xlog_newpage(XLogRecPtr lsn, XLogRecord *record)
  {
***************
*** 7429,7434 **** heap2_redo(XLogRecPtr lsn, XLogRecord *record)
--- 7831,7839 ----
  		case XLOG_HEAP2_CLEAN:
  			heap_xlog_clean(lsn, record);
  			break;
+ 		case XLOG_HEAP2_FREEZE_PAGE:
+ 			heap_xlog_freeze_page(lsn, record);
+ 			break;
  		case XLOG_HEAP2_CLEANUP_INFO:
  			heap_xlog_cleanup_info(lsn, record);
  			break;
*** a/src/backend/access/rmgrdesc/heapdesc.c
--- b/src/backend/access/rmgrdesc/heapdesc.c
***************
*** 149,154 **** heap2_desc(StringInfo buf, uint8 xl_info, char *rec)
--- 149,163 ----
  						 xlrec->node.relNode, xlrec->block,
  						 xlrec->latestRemovedXid);
  	}
+ 	else if (info == XLOG_HEAP2_FREEZE_PAGE)
+ 	{
+ 		xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) rec;
+ 
+ 		appendStringInfo(buf, "freeze_page: rel %u/%u/%u; blk %u; cutoff xid %u ntuples %u",
+ 						 xlrec->node.spcNode, xlrec->node.dbNode,
+ 						 xlrec->node.relNode, xlrec->block,
+ 						 xlrec->cutoff_xid, xlrec->ntuples);
+ 	}
  	else if (info == XLOG_HEAP2_CLEANUP_INFO)
  	{
  		xl_heap_cleanup_info *xlrec = (xl_heap_cleanup_info *) rec;
*** a/src/backend/access/transam/multixact.c
--- b/src/backend/access/transam/multixact.c
***************
*** 286,292 **** static MemoryContext MXactContext = NULL;
  
  /* internal MultiXactId management */
  static void MultiXactIdSetOldestVisible(void);
- static MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members);
  static void RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
  				   int nmembers, MultiXactMember *members);
  static MultiXactId GetNewMultiXactId(int nmembers, MultiXactOffset *offset);
--- 286,291 ----
***************
*** 344,350 **** MultiXactIdCreate(TransactionId xid1, MultiXactStatus status1,
  	members[1].xid = xid2;
  	members[1].status = status2;
  
! 	newMulti = CreateMultiXactId(2, members);
  
  	debug_elog3(DEBUG2, "Create: %s",
  				mxid_to_string(newMulti, 2, members));
--- 343,349 ----
  	members[1].xid = xid2;
  	members[1].status = status2;
  
! 	newMulti = MultiXactIdCreateFromMembers(2, members);
  
  	debug_elog3(DEBUG2, "Create: %s",
  				mxid_to_string(newMulti, 2, members));
***************
*** 407,413 **** MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
  		 */
  		member.xid = xid;
  		member.status = status;
! 		newMulti = CreateMultiXactId(1, &member);
  
  		debug_elog4(DEBUG2, "Expand: %u has no members, create singleton %u",
  					multi, newMulti);
--- 406,412 ----
  		 */
  		member.xid = xid;
  		member.status = status;
! 		newMulti = MultiXactIdCreateFromMembers(1, &member);
  
  		debug_elog4(DEBUG2, "Expand: %u has no members, create singleton %u",
  					multi, newMulti);
***************
*** 459,465 **** MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
  
  	newMembers[j].xid = xid;
  	newMembers[j++].status = status;
! 	newMulti = CreateMultiXactId(j, newMembers);
  
  	pfree(members);
  	pfree(newMembers);
--- 458,464 ----
  
  	newMembers[j].xid = xid;
  	newMembers[j++].status = status;
! 	newMulti = MultiXactIdCreateFromMembers(j, newMembers);
  
  	pfree(members);
  	pfree(newMembers);
***************
*** 664,679 **** ReadNextMultiXactId(void)
  }
  
  /*
!  * CreateMultiXactId
!  *		Make a new MultiXactId
   *
   * Make XLOG, SLRU and cache entries for a new MultiXactId, recording the
   * given TransactionIds as members.  Returns the newly created MultiXactId.
   *
   * NB: the passed members[] array will be sorted in-place.
   */
! static MultiXactId
! CreateMultiXactId(int nmembers, MultiXactMember *members)
  {
  	MultiXactId multi;
  	MultiXactOffset offset;
--- 663,678 ----
  }
  
  /*
!  * MultiXactIdCreateFromMembers
!  *		Make a new MultiXactId from the specified set of members
   *
   * Make XLOG, SLRU and cache entries for a new MultiXactId, recording the
   * given TransactionIds as members.  Returns the newly created MultiXactId.
   *
   * NB: the passed members[] array will be sorted in-place.
   */
! MultiXactId
! MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
  {
  	MultiXactId multi;
  	MultiXactOffset offset;
***************
*** 760,766 **** CreateMultiXactId(int nmembers, MultiXactMember *members)
   * RecordNewMultiXact
   *		Write info about a new multixact into the offsets and members files
   *
!  * This is broken out of CreateMultiXactId so that xlog replay can use it.
   */
  static void
  RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
--- 759,766 ----
   * RecordNewMultiXact
   *		Write info about a new multixact into the offsets and members files
   *
!  * This is broken out of MultiXactIdCreateFromMembers so that xlog replay can
!  * use it.
   */
  static void
  RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
*** a/src/backend/commands/vacuumlazy.c
--- b/src/backend/commands/vacuumlazy.c
***************
*** 424,429 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 424,430 ----
  	Buffer		vmbuffer = InvalidBuffer;
  	BlockNumber next_not_all_visible_block;
  	bool		skipping_all_visible_blocks;
+ 	xl_heap_freeze_tuple *frozen;
  
  	pg_rusage_init(&ru0);
  
***************
*** 446,451 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 447,453 ----
  	vacrelstats->latestRemovedXid = InvalidTransactionId;
  
  	lazy_space_alloc(vacrelstats, nblocks);
+ 	frozen = palloc(sizeof(xl_heap_freeze_tuple) * MaxHeapTuplesPerPage);
  
  	/*
  	 * We want to skip pages that don't require vacuuming according to the
***************
*** 500,506 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  		bool		tupgone,
  					hastup;
  		int			prev_dead_count;
- 		OffsetNumber frozen[MaxOffsetNumber];
  		int			nfrozen;
  		Size		freespace;
  		bool		all_visible_according_to_vm;
--- 502,507 ----
***************
*** 893,901 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  				 * Each non-removable tuple must be checked to see if it needs
  				 * freezing.  Note we already have exclusive buffer lock.
  				 */
! 				if (heap_freeze_tuple(tuple.t_data, FreezeLimit,
! 									  MultiXactCutoff))
! 					frozen[nfrozen++] = offnum;
  			}
  		}						/* scan along page */
  
--- 894,902 ----
  				 * Each non-removable tuple must be checked to see if it needs
  				 * freezing.  Note we already have exclusive buffer lock.
  				 */
! 				if (heap_prepare_freeze_tuple(tuple.t_data, FreezeLimit,
! 										  MultiXactCutoff, &frozen[nfrozen]))
! 					frozen[nfrozen++].offset = offnum;
  			}
  		}						/* scan along page */
  
***************
*** 906,920 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  		 */
  		if (nfrozen > 0)
  		{
  			MarkBufferDirty(buf);
  			if (RelationNeedsWAL(onerel))
  			{
  				XLogRecPtr	recptr;
  
  				recptr = log_heap_freeze(onerel, buf, FreezeLimit,
! 										 MultiXactCutoff, frozen, nfrozen);
  				PageSetLSN(page, recptr);
  			}
  		}
  
  		/*
--- 907,939 ----
  		 */
  		if (nfrozen > 0)
  		{
+ 			START_CRIT_SECTION();
+ 
  			MarkBufferDirty(buf);
+ 
+ 			/* execute collected freezes */
+ 			for (i = 0; i < nfrozen; i++)
+ 			{
+ 				ItemId		itemid;
+ 				HeapTupleHeader htup;
+ 
+ 				itemid = PageGetItemId(page, frozen[i].offset);
+ 				htup = (HeapTupleHeader) PageGetItem(page, itemid);
+ 
+ 				heap_execute_freeze_tuple(htup, &frozen[i]);
+ 			}
+ 
+ 			/* Now WAL-log freezing if neccessary */
  			if (RelationNeedsWAL(onerel))
  			{
  				XLogRecPtr	recptr;
  
  				recptr = log_heap_freeze(onerel, buf, FreezeLimit,
! 										 frozen, nfrozen);
  				PageSetLSN(page, recptr);
  			}
+ 
+ 			END_CRIT_SECTION();
  		}
  
  		/*
***************
*** 1015,1020 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 1034,1041 ----
  			RecordPageWithFreeSpace(onerel, blkno, freespace);
  	}
  
+ 	pfree(frozen);
+ 
  	/* save stats for use later */
  	vacrelstats->scanned_tuples = num_tuples;
  	vacrelstats->tuples_deleted = tups_vacuumed;
*** a/src/include/access/heapam_xlog.h
--- b/src/include/access/heapam_xlog.h
***************
*** 50,56 ****
   */
  #define XLOG_HEAP2_FREEZE		0x00
  #define XLOG_HEAP2_CLEAN		0x10
! /* 0x20 is free, was XLOG_HEAP2_CLEAN_MOVE */
  #define XLOG_HEAP2_CLEANUP_INFO 0x30
  #define XLOG_HEAP2_VISIBLE		0x40
  #define XLOG_HEAP2_MULTI_INSERT 0x50
--- 50,56 ----
   */
  #define XLOG_HEAP2_FREEZE		0x00
  #define XLOG_HEAP2_CLEAN		0x10
! #define XLOG_HEAP2_FREEZE_PAGE	0x20
  #define XLOG_HEAP2_CLEANUP_INFO 0x30
  #define XLOG_HEAP2_VISIBLE		0x40
  #define XLOG_HEAP2_MULTI_INSERT 0x50
***************
*** 239,245 **** typedef struct xl_heap_inplace
  
  #define SizeOfHeapInplace	(offsetof(xl_heap_inplace, target) + SizeOfHeapTid)
  
! /* This is what we need to know about tuple freezing during vacuum */
  typedef struct xl_heap_freeze
  {
  	RelFileNode node;
--- 239,245 ----
  
  #define SizeOfHeapInplace	(offsetof(xl_heap_inplace, target) + SizeOfHeapTid)
  
! /* This is what we need to know about tuple freezing during vacuum (legacy) */
  typedef struct xl_heap_freeze
  {
  	RelFileNode node;
***************
*** 251,256 **** typedef struct xl_heap_freeze
--- 251,287 ----
  
  #define SizeOfHeapFreeze (offsetof(xl_heap_freeze, cutoff_multi) + sizeof(MultiXactId))
  
+ /*
+  * a 'freeze plan' struct that represents what we need to know about a single
+  * tuple being frozen during vacuum
+  */
+ #define		XLH_FREEZE_XMIN		0x01
+ #define		XLH_FREEZE_XVAC		0x02
+ #define		XLH_INVALID_XVAC	0x04
+ 
+ typedef struct xl_heap_freeze_tuple
+ {
+ 	TransactionId xmax;
+ 	OffsetNumber offset;
+ 	uint16		t_infomask2;
+ 	uint16		t_infomask;
+ 	uint8		frzflags;
+ } xl_heap_freeze_tuple;
+ 
+ /*
+  * This is what we need to know about a block being frozen during vacuum
+  */
+ typedef struct xl_heap_freeze_page
+ {
+ 	RelFileNode node;
+ 	BlockNumber block;
+ 	TransactionId cutoff_xid;
+ 	uint16		ntuples;
+ 	xl_heap_freeze_tuple tuples[FLEXIBLE_ARRAY_MEMBER];
+ } xl_heap_freeze_page;
+ 
+ #define SizeOfHeapFreezePage offsetof(xl_heap_freeze_page, tuples)
+ 
  /* This is what we need to know about setting a visibility map bit */
  typedef struct xl_heap_visible
  {
***************
*** 277,284 **** extern XLogRecPtr log_heap_clean(Relation reln, Buffer buffer,
  			   OffsetNumber *nowunused, int nunused,
  			   TransactionId latestRemovedXid);
  extern XLogRecPtr log_heap_freeze(Relation reln, Buffer buffer,
! 				TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				OffsetNumber *offsets, int offcnt);
  extern XLogRecPtr log_heap_visible(RelFileNode rnode, Buffer heap_buffer,
  				 Buffer vm_buffer, TransactionId cutoff_xid);
  extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
--- 308,321 ----
  			   OffsetNumber *nowunused, int nunused,
  			   TransactionId latestRemovedXid);
  extern XLogRecPtr log_heap_freeze(Relation reln, Buffer buffer,
! 				TransactionId cutoff_xid, xl_heap_freeze_tuple *tuples,
! 				int ntuples);
! extern bool heap_prepare_freeze_tuple(HeapTupleHeader tuple,
! 						  TransactionId cutoff_xid,
! 						  TransactionId cutoff_multi,
! 						  xl_heap_freeze_tuple *frz);
! extern void heap_execute_freeze_tuple(HeapTupleHeader tuple,
! 						  xl_heap_freeze_tuple *xlrec_tp);
  extern XLogRecPtr log_heap_visible(RelFileNode rnode, Buffer heap_buffer,
  				 Buffer vm_buffer, TransactionId cutoff_xid);
  extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
*** a/src/include/access/multixact.h
--- b/src/include/access/multixact.h
***************
*** 81,86 **** extern MultiXactId MultiXactIdCreate(TransactionId xid1,
--- 81,89 ----
  				  MultiXactStatus status2);
  extern MultiXactId MultiXactIdExpand(MultiXactId multi, TransactionId xid,
  				  MultiXactStatus status);
+ extern MultiXactId MultiXactIdCreateFromMembers(int nmembers,
+ 							 MultiXactMember *members);
+ 
  extern MultiXactId ReadNextMultiXactId(void);
  extern bool MultiXactIdIsRunning(MultiXactId multi);
  extern void MultiXactIdSetOldestMember(void);
*** a/src/include/access/xlog.h
--- b/src/include/access/xlog.h
***************
*** 212,217 **** extern int	wal_level;
--- 212,218 ----
  /* Do we need to WAL-log information required only for Hot Standby? */
  #define XLogStandbyInfoActive() (wal_level >= WAL_LEVEL_HOT_STANDBY)
  
+ #define WAL_DEBUG
  #ifdef WAL_DEBUG
  extern bool XLOG_DEBUG;
  #endif

*** a/src/backend/access/heap/heapam.c
--- b/src/backend/access/heap/heapam.c
***************
*** 5409,5422 **** heap_inplace_update(Relation relation, HeapTuple tuple)
  		CacheInvalidateHeapTuple(relation, tuple, NULL);
  }
  
  
  /*
!  * heap_freeze_tuple
   *
   * Check to see whether any of the XID fields of a tuple (xmin, xmax, xvac)
!  * are older than the specified cutoff XID.  If so, replace them with
!  * FrozenTransactionId or InvalidTransactionId as appropriate, and return
!  * TRUE.  Return FALSE if nothing was changed.
   *
   * It is assumed that the caller has checked the tuple with
   * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
--- 5409,5669 ----
  		CacheInvalidateHeapTuple(relation, tuple, NULL);
  }
  
+ #define		FRM_NOOP				0x0001
+ #define		FRM_INVALIDATE_XMAX		0x0002
+ #define		FRM_RETURN_IS_XID		0x0004
+ #define		FRM_RETURN_IS_MULTI		0x0008
+ #define		FRM_MARK_COMMITTED		0x0010
  
  /*
!  * FreezeMultiXactId
!  *		Determine what to do during freezing when a tuple is marked by a
!  *		MultiXactId.
!  *
!  * NB -- this might have the side-effect of creating a new MultiXactId!
!  *
!  * "flags" is an output value; it's used to tell caller what to do on return.
!  * Possible flags are:
!  * FRM_NOOP
!  *		don't do anything -- keep existing Xmax
!  * FRM_INVALIDATE_XMAX
!  *		mark Xmax as InvalidTransactionId and set XMAX_INVALID flag.
!  * FRM_RETURN_IS_XID
!  *		The Xid return value is a single update Xid to set as xmax.
!  * FRM_MARK_COMMITTED
!  *		Xmax can be marked as HEAP_XMAX_COMMITTED
!  * FRM_RETURN_IS_MULTI
!  *		The return value is a new MultiXactId to set as new Xmax.
!  *		(caller must obtain proper infomask bits using GetMultiXactIdHintBits)
!  */
! static TransactionId
! FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
! 				  TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				  uint16 *flags)
! {
! 	TransactionId xid = InvalidTransactionId;
! 	int			i;
! 	MultiXactMember *members;
! 	int			nmembers;
! 	bool		need_replace;
! 	int			nnewmembers;
! 	MultiXactMember *newmembers;
! 	bool		has_lockers;
! 	TransactionId update_xid;
! 	bool		update_committed;
! 
! 	*flags = 0;
! 
! 	/* We should only be called in Multis */
! 	Assert(t_infomask & HEAP_XMAX_IS_MULTI);
! 
! 	if (!MultiXactIdIsValid(multi))
! 	{
! 		/* Ensure infomask bits are appropriately set/reset */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		return InvalidTransactionId;
! 	}
! 	else if (MultiXactIdPrecedes(multi, cutoff_multi))
! 	{
! 		/*
! 		 * This old multi cannot possibly have members still running.  If it
! 		 * was a locker only, it can be removed without any further
! 		 * consideration; but if it contained an update, we might need to
! 		 * preserve it.
! 		 */
! 		Assert(!MultiXactIdIsRunning(multi));
! 		if (HEAP_XMAX_IS_LOCKED_ONLY(t_infomask))
! 		{
! 			*flags |= FRM_INVALIDATE_XMAX;
! 			xid = InvalidTransactionId; /* not strictly necessary */
! 		}
! 		else
! 		{
! 			/* replace multi by update xid */
! 			xid = MultiXactIdGetUpdateXid(multi, t_infomask);
! 
! 			/* wasn't only a lock, xid needs to be valid */
! 			Assert(TransactionIdIsValid(xid));
! 
! 			/*
! 			 * If the xid is older than the cutoff, it has to have aborted,
! 			 * otherwise the tuple would have gotten pruned away.
! 			 */
! 			if (TransactionIdPrecedes(xid, cutoff_xid))
! 			{
! 				Assert(!TransactionIdDidCommit(xid));
! 				*flags |= FRM_INVALIDATE_XMAX;
! 				xid = InvalidTransactionId;		/* not strictly necessary */
! 			}
! 			else
! 				*flags |= FRM_RETURN_IS_XID;
! 		}
! 
! 		return xid;
! 	}
! 
! 	/*
! 	 * This multixact might have or might not have members still running, but
! 	 * we know it's valid and is newer than the cutoff point for multis.
! 	 * However, some member(s) of it may be below the cutoff for Xids, so we
! 	 * need to walk the whole members array to figure out what to do, if
! 	 * anything.
! 	 */
! 
! 	nmembers = GetMultiXactIdMembers(multi, &members, false);
! 	if (nmembers <= 0)
! 	{
! 		/* Nothing worth keeping */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		return InvalidTransactionId;
! 	}
! 
! 	/* is there anything older than the cutoff? */
! 	need_replace = false;
! 	for (i = 0; i < nmembers; i++)
! 	{
! 		if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
! 		{
! 			need_replace = true;
! 			break;
! 		}
! 	}
! 
! 	/*
! 	 * In the simplest case, there is no member older than the cutoff; we can
! 	 * keep the existing MultiXactId as is.
! 	 */
! 	if (!need_replace)
! 	{
! 		*flags |= FRM_NOOP;
! 		pfree(members);
! 		return InvalidTransactionId;
! 	}
! 
! 	/*
! 	 * If the multi needs to be updated, figure out which members do we need
! 	 * to keep.
! 	 */
! 	nnewmembers = 0;
! 	newmembers = palloc(sizeof(MultiXactMember) * nmembers);
! 	has_lockers = false;
! 	update_xid = InvalidTransactionId;
! 	update_committed = false;
! 
! 	for (i = 0; i < nmembers; i++)
! 	{
! 		if (ISUPDATE_from_mxstatus(members[i].status))
! 		{
! 			/*
! 			 * It's an update; should we keep it?  If the transaction is known
! 			 * aborted then it's okay to ignore it, otherwise not.  (Note this
! 			 * is just an optimization and not needed for correctness, so it's
! 			 * okay to get this test wrong; for example, in case an updater is
! 			 * crashed, or a running transaction in the process of aborting.)
! 			 */
! 			if (!TransactionIdDidAbort(members[i].xid))
! 			{
! 				newmembers[nnewmembers++] = members[i];
! 				Assert(!TransactionIdIsValid(update_xid));
! 
! 				/*
! 				 * Tell caller to set HEAP_XMAX_COMMITTED hint while we have
! 				 * the Xid in cache.  Again, this is just an optimization, so
! 				 * it's not a problem if the transaction is still running and
! 				 * in the process of committing.
! 				 */
! 				if (TransactionIdDidCommit(update_xid))
! 					update_committed = true;
! 
! 				update_xid = newmembers[i].xid;
! 			}
! 
! 			/*
! 			 * Checking for very old update Xids is critical: if the update
! 			 * member of the multi is older than cutoff_xid, we must remove
! 			 * it, because otherwise a later liveliness check could attempt
! 			 * pg_clog access for a page that was truncated away by the
! 			 * current vacuum.	Note that if the update had committed, we
! 			 * wouldn't be freezing this tuple because it would have gotten
! 			 * removed (HEAPTUPLE_DEAD) by HeapTupleSatisfiesVacuum; so it
! 			 * either aborted or crashed.  Therefore, ignore this update_xid.
! 			 */
! 			if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 			{
! 				update_xid = InvalidTransactionId;
! 				update_committed = false;
! 
! 			}
! 		}
! 		else
! 		{
! 			/* We only keep lockers if they are still running */
! 			if (TransactionIdIsCurrentTransactionId(members[i].xid) ||
! 				TransactionIdIsInProgress(members[i].xid))
! 			{
! 				/* running locker cannot possibly be older than the cutoff */
! 				Assert(!TransactionIdPrecedes(members[i].xid, cutoff_xid));
! 				newmembers[nnewmembers++] = members[i];
! 				has_lockers = true;
! 			}
! 		}
! 	}
! 
! 	pfree(members);
! 
! 	if (nnewmembers == 0)
! 	{
! 		/* nothing worth keeping!? Tell caller to remove the whole thing */
! 		*flags |= FRM_INVALIDATE_XMAX;
! 		xid = InvalidTransactionId;
! 	}
! 	else if (TransactionIdIsValid(update_xid) && !has_lockers)
! 	{
! 		/*
! 		 * If there's a single member and it's an update, pass it back alone
! 		 * without creating a new Multi.  (XXX we could do this when there's a
! 		 * single remaining locker, too, but that would complicate the API too
! 		 * much; moreover, the case with the single updater is more
! 		 * interesting, because those are longer-lived.)
! 		 */
! 		Assert(nnewmembers == 1);
! 		*flags |= FRM_RETURN_IS_XID;
! 		if (update_committed)
! 			*flags |= FRM_MARK_COMMITTED;
! 		xid = update_xid;
! 	}
! 	else
! 	{
! 		/*
! 		 * Create a new multixact with the surviving members of the previous
! 		 * one, to set as new Xmax in the tuple.
! 		 *
! 		 * If this is the first possibly-multixact-able operation in the
! 		 * current transaction, set my per-backend OldestMemberMXactId
! 		 * setting. We can be certain that the transaction will never become a
! 		 * member of any older MultiXactIds than that.
! 		 */
! 		MultiXactIdSetOldestMember();
! 		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers);
! 		*flags |= FRM_RETURN_IS_MULTI;
! 	}
! 
! 	pfree(newmembers);
! 
! 	return xid;
! }
! 
! /*
!  * heap_prepare_freeze_tuple
   *
   * Check to see whether any of the XID fields of a tuple (xmin, xmax, xvac)
!  * are older than the specified cutoff XID and cutoff MultiXactId.	If so,
!  * setup enough state (in the *frz output argument) to later execute and
!  * WAL-log what we would need to do, and return TRUE.  Return FALSE if nothing
!  * is to be changed.
!  *
!  * Caller is responsible for setting the offset field, if appropriate.	This
!  * is only necessary if the freeze is to be WAL-logged.
   *
   * It is assumed that the caller has checked the tuple with
   * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
***************
*** 5425,5478 **** heap_inplace_update(Relation relation, HeapTuple tuple)
   * NB: cutoff_xid *must* be <= the current global xmin, to ensure that any
   * XID older than it could neither be running nor seen as running by any
   * open transaction.  This ensures that the replacement will not change
!  * anyone's idea of the tuple state.  Also, since we assume the tuple is
!  * not HEAPTUPLE_DEAD, the fact that an XID is not still running allows us
!  * to assume that it is either committed good or aborted, as appropriate;
!  * so we need no external state checks to decide what to do.  (This is good
!  * because this function is applied during WAL recovery, when we don't have
!  * access to any such state, and can't depend on the hint bits to be set.)
!  * There is an exception we make which is to assume GetMultiXactIdMembers can
!  * be called during recovery.
!  *
   * Similarly, cutoff_multi must be less than or equal to the smallest
   * MultiXactId used by any transaction currently open.
   *
   * If the tuple is in a shared buffer, caller must hold an exclusive lock on
   * that buffer.
   *
!  * Note: it might seem we could make the changes without exclusive lock, since
!  * TransactionId read/write is assumed atomic anyway.  However there is a race
!  * condition: someone who just fetched an old XID that we overwrite here could
!  * conceivably not finish checking the XID against pg_clog before we finish
!  * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
!  * exclusive lock ensures no other backend is in process of checking the
!  * tuple status.  Also, getting exclusive lock makes it safe to adjust the
!  * infomask bits.
!  *
!  * NB: Cannot rely on hint bits here, they might not be set after a crash or
!  * on a standby.
   */
  bool
! heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
! 				  MultiXactId cutoff_multi)
  {
  	bool		changed = false;
  	bool		freeze_xmax = false;
  	TransactionId xid;
  
  	/* Process xmin */
  	xid = HeapTupleHeaderGetXmin(tuple);
  	if (TransactionIdIsNormal(xid) &&
  		TransactionIdPrecedes(xid, cutoff_xid))
  	{
! 		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
  
  		/*
  		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
  		 * already be set here, but there's a small chance not.
  		 */
! 		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
  		changed = true;
  	}
  
--- 5672,5715 ----
   * NB: cutoff_xid *must* be <= the current global xmin, to ensure that any
   * XID older than it could neither be running nor seen as running by any
   * open transaction.  This ensures that the replacement will not change
!  * anyone's idea of the tuple state.
   * Similarly, cutoff_multi must be less than or equal to the smallest
   * MultiXactId used by any transaction currently open.
   *
   * If the tuple is in a shared buffer, caller must hold an exclusive lock on
   * that buffer.
   *
!  * NB: It is not enough to set hint bits to indicate something is
!  * committed/invalid -- they might not be set on a standby, or after crash
!  * recovery.  We really need to remove old xids.
   */
  bool
! heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
! 						  TransactionId cutoff_multi,
! 						  xl_heap_freeze_tuple *frz)
! 
  {
  	bool		changed = false;
  	bool		freeze_xmax = false;
  	TransactionId xid;
  
+ 	frz->frzflags = 0;
+ 	frz->t_infomask2 = tuple->t_infomask2;
+ 	frz->t_infomask = tuple->t_infomask;
+ 	frz->xmax = HeapTupleHeaderGetRawXmax(tuple);
+ 
  	/* Process xmin */
  	xid = HeapTupleHeaderGetXmin(tuple);
  	if (TransactionIdIsNormal(xid) &&
  		TransactionIdPrecedes(xid, cutoff_xid))
  	{
! 		frz->frzflags |= XLH_FREEZE_XMIN;
  
  		/*
  		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
  		 * already be set here, but there's a small chance not.
  		 */
! 		frz->t_infomask |= HEAP_XMIN_COMMITTED;
  		changed = true;
  	}
  
***************
*** 5489,5579 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  
  	if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
  	{
! 		if (!MultiXactIdIsValid(xid))
! 		{
! 			/* no xmax set, ignore */
! 			;
! 		}
! 		else if (MultiXactIdPrecedes(xid, cutoff_multi))
! 		{
! 			/*
! 			 * This old multi cannot possibly be running.  If it was a locker
! 			 * only, it can be removed without much further thought; but if it
! 			 * contained an update, we need to preserve it.
! 			 */
! 			if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
! 				freeze_xmax = true;
! 			else
! 			{
! 				TransactionId update_xid;
! 
! 				update_xid = HeapTupleGetUpdateXid(tuple);
  
! 				/*
! 				 * The multixact has an update hidden within.  Get rid of it.
! 				 *
! 				 * If the update_xid is below the cutoff_xid, it necessarily
! 				 * must be an aborted transaction.  In a primary server, such
! 				 * an Xmax would have gotten marked invalid by
! 				 * HeapTupleSatisfiesVacuum, but in a replica that is not
! 				 * called before we are, so deal with it in the same way.
! 				 *
! 				 * If not below the cutoff_xid, then the tuple would have been
! 				 * pruned by vacuum, if the update committed long enough ago,
! 				 * and we wouldn't be freezing it; so it's either recently
! 				 * committed, or in-progress.  Deal with this by setting the
! 				 * Xmax to the update Xid directly and remove the IS_MULTI
! 				 * bit.  (We know there cannot be running lockers in this
! 				 * multi, because it's below the cutoff_multi value.)
! 				 */
  
! 				if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 				{
! 					Assert(InRecovery || TransactionIdDidAbort(update_xid));
! 					freeze_xmax = true;
! 				}
! 				else
! 				{
! 					Assert(InRecovery || !TransactionIdIsInProgress(update_xid));
! 					tuple->t_infomask &= ~HEAP_XMAX_BITS;
! 					HeapTupleHeaderSetXmax(tuple, update_xid);
! 					changed = true;
! 				}
! 			}
  		}
! 		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
  		{
! 			/* newer than the cutoff, so don't touch it */
! 			;
  		}
  		else
  		{
! 			TransactionId	update_xid;
! 
! 			/*
! 			 * This is a multixact which is not marked LOCK_ONLY, but which
! 			 * is newer than the cutoff_multi.  If the update_xid is below the
! 			 * cutoff_xid point, then we can just freeze the Xmax in the
! 			 * tuple, removing it altogether.  This seems simple, but there
! 			 * are several underlying assumptions:
! 			 *
! 			 * 1. A tuple marked by an multixact containing a very old
! 			 * committed update Xid would have been pruned away by vacuum; we
! 			 * wouldn't be freezing this tuple at all.
! 			 *
! 			 * 2. There cannot possibly be any live locking members remaining
! 			 * in the multixact.  This is because if they were alive, the
! 			 * update's Xid would had been considered, via the lockers'
! 			 * snapshot's Xmin, as part the cutoff_xid.
! 			 *
! 			 * 3. We don't create new MultiXacts via MultiXactIdExpand() that
! 			 * include a very old aborted update Xid: in that function we only
! 			 * include update Xids corresponding to transactions that are
! 			 * committed or in-progress.
! 			 */
! 			update_xid = HeapTupleGetUpdateXid(tuple);
! 			if (TransactionIdPrecedes(update_xid, cutoff_xid))
! 				freeze_xmax = true;
  		}
  	}
  	else if (TransactionIdIsNormal(xid) &&
--- 5726,5760 ----
  
  	if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
  	{
! 		TransactionId newxmax;
! 		uint16		flags;
  
! 		newxmax = FreezeMultiXactId(xid, tuple->t_infomask,
! 									cutoff_xid, cutoff_multi, &flags);
  
! 		if (flags & FRM_INVALIDATE_XMAX)
! 			freeze_xmax = true;
! 		else if (flags & FRM_RETURN_IS_XID)
! 		{
! 			frz->t_infomask &= ~HEAP_XMAX_BITS;
! 			frz->xmax = newxmax;
! 			if (flags & FRM_MARK_COMMITTED)
! 				frz->t_infomask &= HEAP_XMAX_COMMITTED;
! 			changed = true;
  		}
! 		else if (flags & FRM_RETURN_IS_MULTI)
  		{
! 			frz->t_infomask &= ~HEAP_XMAX_BITS;
! 			frz->xmax = newxmax;
! 
! 			GetMultiXactIdHintBits(newxmax,
! 								   &frz->t_infomask,
! 								   &frz->t_infomask2);
! 			changed = true;
  		}
  		else
  		{
! 			Assert(flags & FRM_NOOP);
  		}
  	}
  	else if (TransactionIdIsNormal(xid) &&
***************
*** 5584,5600 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  
  	if (freeze_xmax)
  	{
! 		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
  
  		/*
  		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
  		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
  		 * Also get rid of the HEAP_KEYS_UPDATED bit.
  		 */
! 		tuple->t_infomask &= ~HEAP_XMAX_BITS;
! 		tuple->t_infomask |= HEAP_XMAX_INVALID;
! 		HeapTupleHeaderClearHotUpdated(tuple);
! 		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
  		changed = true;
  	}
  
--- 5765,5781 ----
  
  	if (freeze_xmax)
  	{
! 		frz->xmax = InvalidTransactionId;
  
  		/*
  		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
  		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
  		 * Also get rid of the HEAP_KEYS_UPDATED bit.
  		 */
! 		frz->t_infomask &= ~HEAP_XMAX_BITS;
! 		frz->t_infomask |= HEAP_XMAX_INVALID;
! 		frz->t_infomask2 &= ~HEAP_HOT_UPDATED;
! 		frz->t_infomask2 &= ~HEAP_KEYS_UPDATED;
  		changed = true;
  	}
  
***************
*** 5614,5629 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
  			 * xvac transaction succeeded.
  			 */
  			if (tuple->t_infomask & HEAP_MOVED_OFF)
! 				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
  			else
! 				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
  
  			/*
  			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
  			 * will already be set here, but there's a small chance not.
  			 */
  			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
  			changed = true;
  		}
  	}
--- 5795,5810 ----
  			 * xvac transaction succeeded.
  			 */
  			if (tuple->t_infomask & HEAP_MOVED_OFF)
! 				frz->frzflags |= XLH_INVALID_XVAC;
  			else
! 				frz->frzflags |= XLH_FREEZE_XVAC;
  
  			/*
  			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
  			 * will already be set here, but there's a small chance not.
  			 */
  			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
! 			frz->t_infomask |= HEAP_XMIN_COMMITTED;
  			changed = true;
  		}
  	}
***************
*** 5632,5637 **** heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
--- 5813,5880 ----
  }
  
  /*
+  * heap_execute_freeze_tuple
+  *		Execute the prepared freezing of a tuple.
+  *
+  * Caller is responsible for ensuring that no other backend can access the
+  * storage underlying this tuple, either by holding an exclusive lock on the
+  * buffer containing it (which is what lazy VACUUM does), or by having it by
+  * in private storage (which is what CLUSTER and friends do).
+  *
+  * Note: it might seem we could make the changes without exclusive lock, since
+  * TransactionId read/write is assumed atomic anyway.  However there is a race
+  * condition: someone who just fetched an old XID that we overwrite here could
+  * conceivably not finish checking the XID against pg_clog before we finish
+  * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
+  * exclusive lock ensures no other backend is in process of checking the
+  * tuple status.  Also, getting exclusive lock makes it safe to adjust the
+  * infomask bits.
+  *
+  * NB: All code in here must be safe to execute during crash recovery!
+  */
+ void
+ heap_execute_freeze_tuple(HeapTupleHeader tuple, xl_heap_freeze_tuple *frz)
+ {
+ 	if (frz->frzflags & XLH_FREEZE_XMIN)
+ 		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+ 
+ 	HeapTupleHeaderSetXmax(tuple, frz->xmax);
+ 
+ 	if (frz->frzflags & XLH_FREEZE_XVAC)
+ 		HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+ 
+ 	if (frz->frzflags & XLH_INVALID_XVAC)
+ 		HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+ 
+ 	tuple->t_infomask = frz->t_infomask;
+ 	tuple->t_infomask2 = frz->t_infomask2;
+ }
+ 
+ /*
+  * heap_freeze_tuple - freeze tuple inplace without WAL logging.
+  *
+  * Useful for callers like CLUSTER that perform their own WAL logging.
+  */
+ bool
+ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+ 				  TransactionId cutoff_multi)
+ {
+ 	xl_heap_freeze_tuple frz;
+ 	bool		do_freeze;
+ 
+ 	do_freeze = heap_prepare_freeze_tuple(tuple, cutoff_xid, cutoff_multi, &frz);
+ 
+ 	/*
+ 	 * Note that because this is not a WAL-logged operation, we don't need to
+ 	 * fill in the offset in the freeze record.
+ 	 */
+ 
+ 	if (do_freeze)
+ 		heap_execute_freeze_tuple(tuple, &frz);
+ 	return do_freeze;
+ }
+ 
+ /*
   * For a given MultiXactId, return the hint bits that should be set in the
   * tuple's infomask.
   *
***************
*** 5934,5949 **** heap_tuple_needs_freeze(HeapTupleHeader tuple, TransactionId cutoff_xid,
  		}
  		else if (MultiXactIdPrecedes(multi, cutoff_multi))
  			return true;
- 		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
- 		{
- 			/* only-locker multis don't need internal examination */
- 			;
- 		}
  		else
  		{
! 			if (TransactionIdPrecedes(HeapTupleGetUpdateXid(tuple),
! 									  cutoff_xid))
! 				return true;
  		}
  	}
  	else
--- 6177,6202 ----
  		}
  		else if (MultiXactIdPrecedes(multi, cutoff_multi))
  			return true;
  		else
  		{
! 			MultiXactMember *members;
! 			int			nmembers;
! 			int			i;
! 
! 			/* need to check whether any member of the mxact is too old */
! 
! 			nmembers = GetMultiXactIdMembers(multi, &members, false);
! 
! 			for (i = 0; i < nmembers; i++)
! 			{
! 				if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
! 				{
! 					pfree(members);
! 					return true;
! 				}
! 			}
! 			if (nmembers > 0)
! 				pfree(members);
  		}
  	}
  	else
***************
*** 6193,6237 **** log_heap_clean(Relation reln, Buffer buffer,
  }
  
  /*
!  * Perform XLogInsert for a heap-freeze operation.	Caller must already
!  * have modified the buffer and marked it dirty.
   */
  XLogRecPtr
! log_heap_freeze(Relation reln, Buffer buffer,
! 				TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				OffsetNumber *offsets, int offcnt)
  {
! 	xl_heap_freeze xlrec;
  	XLogRecPtr	recptr;
  	XLogRecData rdata[2];
  
  	/* Caller should not call me on a non-WAL-logged relation */
  	Assert(RelationNeedsWAL(reln));
  	/* nor when there are no tuples to freeze */
! 	Assert(offcnt > 0);
  
  	xlrec.node = reln->rd_node;
  	xlrec.block = BufferGetBlockNumber(buffer);
  	xlrec.cutoff_xid = cutoff_xid;
! 	xlrec.cutoff_multi = cutoff_multi;
  
  	rdata[0].data = (char *) &xlrec;
! 	rdata[0].len = SizeOfHeapFreeze;
  	rdata[0].buffer = InvalidBuffer;
  	rdata[0].next = &(rdata[1]);
  
  	/*
! 	 * The tuple-offsets array is not actually in the buffer, but pretend that
! 	 * it is.  When XLogInsert stores the whole buffer, the offsets array need
  	 * not be stored too.
  	 */
! 	rdata[1].data = (char *) offsets;
! 	rdata[1].len = offcnt * sizeof(OffsetNumber);
  	rdata[1].buffer = buffer;
  	rdata[1].buffer_std = true;
  	rdata[1].next = NULL;
  
! 	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE, rdata);
  
  	return recptr;
  }
--- 6446,6489 ----
  }
  
  /*
!  * Perform XLogInsert for a heap-freeze operation.	Caller must have already
!  * modified the buffer and marked it dirty.
   */
  XLogRecPtr
! log_heap_freeze(Relation reln, Buffer buffer, TransactionId cutoff_xid,
! 				xl_heap_freeze_tuple *tuples, int ntuples)
  {
! 	xl_heap_freeze_page xlrec;
  	XLogRecPtr	recptr;
  	XLogRecData rdata[2];
  
  	/* Caller should not call me on a non-WAL-logged relation */
  	Assert(RelationNeedsWAL(reln));
  	/* nor when there are no tuples to freeze */
! 	Assert(ntuples > 0);
  
  	xlrec.node = reln->rd_node;
  	xlrec.block = BufferGetBlockNumber(buffer);
  	xlrec.cutoff_xid = cutoff_xid;
! 	xlrec.ntuples = ntuples;
  
  	rdata[0].data = (char *) &xlrec;
! 	rdata[0].len = SizeOfHeapFreezePage;
  	rdata[0].buffer = InvalidBuffer;
  	rdata[0].next = &(rdata[1]);
  
  	/*
! 	 * The freeze plan array is not actually in the buffer, but pretend that
! 	 * it is.  When XLogInsert stores the whole buffer, the freeze plan need
  	 * not be stored too.
  	 */
! 	rdata[1].data = (char *) tuples;
! 	rdata[1].len = ntuples * sizeof(xl_heap_freeze_tuple);
  	rdata[1].buffer = buffer;
  	rdata[1].buffer_std = true;
  	rdata[1].next = NULL;
  
! 	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE_PAGE, rdata);
  
  	return recptr;
  }
***************
*** 6839,6902 **** heap_xlog_clean(XLogRecPtr lsn, XLogRecord *record)
  	XLogRecordPageWithFreeSpace(xlrec->node, xlrec->block, freespace);
  }
  
- static void
- heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
- {
- 	xl_heap_freeze *xlrec = (xl_heap_freeze *) XLogRecGetData(record);
- 	TransactionId cutoff_xid = xlrec->cutoff_xid;
- 	MultiXactId cutoff_multi = xlrec->cutoff_multi;
- 	Buffer		buffer;
- 	Page		page;
- 
- 	/*
- 	 * In Hot Standby mode, ensure that there's no queries running which still
- 	 * consider the frozen xids as running.
- 	 */
- 	if (InHotStandby)
- 		ResolveRecoveryConflictWithSnapshot(cutoff_xid, xlrec->node);
- 
- 	/* If we have a full-page image, restore it and we're done */
- 	if (record->xl_info & XLR_BKP_BLOCK(0))
- 	{
- 		(void) RestoreBackupBlock(lsn, record, 0, false, false);
- 		return;
- 	}
- 
- 	buffer = XLogReadBuffer(xlrec->node, xlrec->block, false);
- 	if (!BufferIsValid(buffer))
- 		return;
- 	page = (Page) BufferGetPage(buffer);
- 
- 	if (lsn <= PageGetLSN(page))
- 	{
- 		UnlockReleaseBuffer(buffer);
- 		return;
- 	}
- 
- 	if (record->xl_len > SizeOfHeapFreeze)
- 	{
- 		OffsetNumber *offsets;
- 		OffsetNumber *offsets_end;
- 
- 		offsets = (OffsetNumber *) ((char *) xlrec + SizeOfHeapFreeze);
- 		offsets_end = (OffsetNumber *) ((char *) xlrec + record->xl_len);
- 
- 		while (offsets < offsets_end)
- 		{
- 			/* offsets[] entries are one-based */
- 			ItemId		lp = PageGetItemId(page, *offsets);
- 			HeapTupleHeader tuple = (HeapTupleHeader) PageGetItem(page, lp);
- 
- 			(void) heap_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
- 			offsets++;
- 		}
- 	}
- 
- 	PageSetLSN(page, lsn);
- 	MarkBufferDirty(buffer);
- 	UnlockReleaseBuffer(buffer);
- }
- 
  /*
   * Replay XLOG_HEAP2_VISIBLE record.
   *
--- 7091,7096 ----
***************
*** 7011,7016 **** heap_xlog_visible(XLogRecPtr lsn, XLogRecord *record)
--- 7205,7267 ----
  	}
  }
  
+ /*
+  * Replay XLOG_HEAP2_FREEZE_PAGE records
+  */
+ static void
+ heap_xlog_freeze_page(XLogRecPtr lsn, XLogRecord *record)
+ {
+ 	xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) XLogRecGetData(record);
+ 	TransactionId cutoff_xid = xlrec->cutoff_xid;
+ 	Buffer		buffer;
+ 	Page		page;
+ 	int			ntup;
+ 
+ 	/*
+ 	 * In Hot Standby mode, ensure that there's no queries running which still
+ 	 * consider the frozen xids as running.
+ 	 */
+ 	if (InHotStandby)
+ 		ResolveRecoveryConflictWithSnapshot(cutoff_xid, xlrec->node);
+ 
+ 	/* If we have a full-page image, restore it and we're done */
+ 	if (record->xl_info & XLR_BKP_BLOCK(0))
+ 	{
+ 		(void) RestoreBackupBlock(lsn, record, 0, false, false);
+ 		return;
+ 	}
+ 
+ 	buffer = XLogReadBuffer(xlrec->node, xlrec->block, false);
+ 	if (!BufferIsValid(buffer))
+ 		return;
+ 
+ 	page = (Page) BufferGetPage(buffer);
+ 
+ 	if (lsn <= PageGetLSN(page))
+ 	{
+ 		UnlockReleaseBuffer(buffer);
+ 		return;
+ 	}
+ 
+ 	/* now execute freeze plan for each frozen tuple */
+ 	for (ntup = 0; ntup < xlrec->ntuples; ntup++)
+ 	{
+ 		xl_heap_freeze_tuple *xlrec_tp;
+ 		ItemId		lp;
+ 		HeapTupleHeader tuple;
+ 
+ 		xlrec_tp = &xlrec->tuples[ntup];
+ 		lp = PageGetItemId(page, xlrec_tp->offset);		/* offsets are one-based */
+ 		tuple = (HeapTupleHeader) PageGetItem(page, lp);
+ 
+ 		heap_execute_freeze_tuple(tuple, xlrec_tp);
+ 	}
+ 
+ 	PageSetLSN(page, lsn);
+ 	MarkBufferDirty(buffer);
+ 	UnlockReleaseBuffer(buffer);
+ }
+ 
  static void
  heap_xlog_newpage(XLogRecPtr lsn, XLogRecord *record)
  {
***************
*** 7874,7885 **** heap2_redo(XLogRecPtr lsn, XLogRecord *record)
  
  	switch (info & XLOG_HEAP_OPMASK)
  	{
- 		case XLOG_HEAP2_FREEZE:
- 			heap_xlog_freeze(lsn, record);
- 			break;
  		case XLOG_HEAP2_CLEAN:
  			heap_xlog_clean(lsn, record);
  			break;
  		case XLOG_HEAP2_CLEANUP_INFO:
  			heap_xlog_cleanup_info(lsn, record);
  			break;
--- 8125,8136 ----
  
  	switch (info & XLOG_HEAP_OPMASK)
  	{
  		case XLOG_HEAP2_CLEAN:
  			heap_xlog_clean(lsn, record);
  			break;
+ 		case XLOG_HEAP2_FREEZE_PAGE:
+ 			heap_xlog_freeze_page(lsn, record);
+ 			break;
  		case XLOG_HEAP2_CLEANUP_INFO:
  			heap_xlog_cleanup_info(lsn, record);
  			break;
*** a/src/backend/access/rmgrdesc/heapdesc.c
--- b/src/backend/access/rmgrdesc/heapdesc.c
***************
*** 131,153 **** heap2_desc(StringInfo buf, uint8 xl_info, char *rec)
  	uint8		info = xl_info & ~XLR_INFO_MASK;
  
  	info &= XLOG_HEAP_OPMASK;
! 	if (info == XLOG_HEAP2_FREEZE)
  	{
! 		xl_heap_freeze *xlrec = (xl_heap_freeze *) rec;
  
! 		appendStringInfo(buf, "freeze: rel %u/%u/%u; blk %u; cutoff xid %u multi %u",
  						 xlrec->node.spcNode, xlrec->node.dbNode,
  						 xlrec->node.relNode, xlrec->block,
! 						 xlrec->cutoff_xid, xlrec->cutoff_multi);
  	}
! 	else if (info == XLOG_HEAP2_CLEAN)
  	{
! 		xl_heap_clean *xlrec = (xl_heap_clean *) rec;
  
! 		appendStringInfo(buf, "clean: rel %u/%u/%u; blk %u remxid %u",
  						 xlrec->node.spcNode, xlrec->node.dbNode,
  						 xlrec->node.relNode, xlrec->block,
! 						 xlrec->latestRemovedXid);
  	}
  	else if (info == XLOG_HEAP2_CLEANUP_INFO)
  	{
--- 131,153 ----
  	uint8		info = xl_info & ~XLR_INFO_MASK;
  
  	info &= XLOG_HEAP_OPMASK;
! 	if (info == XLOG_HEAP2_CLEAN)
  	{
! 		xl_heap_clean *xlrec = (xl_heap_clean *) rec;
  
! 		appendStringInfo(buf, "clean: rel %u/%u/%u; blk %u remxid %u",
  						 xlrec->node.spcNode, xlrec->node.dbNode,
  						 xlrec->node.relNode, xlrec->block,
! 						 xlrec->latestRemovedXid);
  	}
! 	else if (info == XLOG_HEAP2_FREEZE_PAGE)
  	{
! 		xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) rec;
  
! 		appendStringInfo(buf, "freeze_page: rel %u/%u/%u; blk %u; cutoff xid %u ntuples %u",
  						 xlrec->node.spcNode, xlrec->node.dbNode,
  						 xlrec->node.relNode, xlrec->block,
! 						 xlrec->cutoff_xid, xlrec->ntuples);
  	}
  	else if (info == XLOG_HEAP2_CLEANUP_INFO)
  	{
*** a/src/backend/access/transam/multixact.c
--- b/src/backend/access/transam/multixact.c
***************
*** 286,292 **** static MemoryContext MXactContext = NULL;
  
  /* internal MultiXactId management */
  static void MultiXactIdSetOldestVisible(void);
- static MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members);
  static void RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
  				   int nmembers, MultiXactMember *members);
  static MultiXactId GetNewMultiXactId(int nmembers, MultiXactOffset *offset);
--- 286,291 ----
***************
*** 344,350 **** MultiXactIdCreate(TransactionId xid1, MultiXactStatus status1,
  	members[1].xid = xid2;
  	members[1].status = status2;
  
! 	newMulti = CreateMultiXactId(2, members);
  
  	debug_elog3(DEBUG2, "Create: %s",
  				mxid_to_string(newMulti, 2, members));
--- 343,349 ----
  	members[1].xid = xid2;
  	members[1].status = status2;
  
! 	newMulti = MultiXactIdCreateFromMembers(2, members);
  
  	debug_elog3(DEBUG2, "Create: %s",
  				mxid_to_string(newMulti, 2, members));
***************
*** 407,413 **** MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
  		 */
  		member.xid = xid;
  		member.status = status;
! 		newMulti = CreateMultiXactId(1, &member);
  
  		debug_elog4(DEBUG2, "Expand: %u has no members, create singleton %u",
  					multi, newMulti);
--- 406,412 ----
  		 */
  		member.xid = xid;
  		member.status = status;
! 		newMulti = MultiXactIdCreateFromMembers(1, &member);
  
  		debug_elog4(DEBUG2, "Expand: %u has no members, create singleton %u",
  					multi, newMulti);
***************
*** 459,465 **** MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
  
  	newMembers[j].xid = xid;
  	newMembers[j++].status = status;
! 	newMulti = CreateMultiXactId(j, newMembers);
  
  	pfree(members);
  	pfree(newMembers);
--- 458,464 ----
  
  	newMembers[j].xid = xid;
  	newMembers[j++].status = status;
! 	newMulti = MultiXactIdCreateFromMembers(j, newMembers);
  
  	pfree(members);
  	pfree(newMembers);
***************
*** 664,679 **** ReadNextMultiXactId(void)
  }
  
  /*
!  * CreateMultiXactId
!  *		Make a new MultiXactId
   *
   * Make XLOG, SLRU and cache entries for a new MultiXactId, recording the
   * given TransactionIds as members.  Returns the newly created MultiXactId.
   *
   * NB: the passed members[] array will be sorted in-place.
   */
! static MultiXactId
! CreateMultiXactId(int nmembers, MultiXactMember *members)
  {
  	MultiXactId multi;
  	MultiXactOffset offset;
--- 663,678 ----
  }
  
  /*
!  * MultiXactIdCreateFromMembers
!  *		Make a new MultiXactId from the specified set of members
   *
   * Make XLOG, SLRU and cache entries for a new MultiXactId, recording the
   * given TransactionIds as members.  Returns the newly created MultiXactId.
   *
   * NB: the passed members[] array will be sorted in-place.
   */
! MultiXactId
! MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
  {
  	MultiXactId multi;
  	MultiXactOffset offset;
***************
*** 760,766 **** CreateMultiXactId(int nmembers, MultiXactMember *members)
   * RecordNewMultiXact
   *		Write info about a new multixact into the offsets and members files
   *
!  * This is broken out of CreateMultiXactId so that xlog replay can use it.
   */
  static void
  RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
--- 759,766 ----
   * RecordNewMultiXact
   *		Write info about a new multixact into the offsets and members files
   *
!  * This is broken out of MultiXactIdCreateFromMembers so that xlog replay can
!  * use it.
   */
  static void
  RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
*** a/src/backend/commands/vacuumlazy.c
--- b/src/backend/commands/vacuumlazy.c
***************
*** 424,429 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 424,430 ----
  	Buffer		vmbuffer = InvalidBuffer;
  	BlockNumber next_not_all_visible_block;
  	bool		skipping_all_visible_blocks;
+ 	xl_heap_freeze_tuple *frozen;
  
  	pg_rusage_init(&ru0);
  
***************
*** 446,451 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 447,453 ----
  	vacrelstats->latestRemovedXid = InvalidTransactionId;
  
  	lazy_space_alloc(vacrelstats, nblocks);
+ 	frozen = palloc(sizeof(xl_heap_freeze_tuple) * MaxHeapTuplesPerPage);
  
  	/*
  	 * We want to skip pages that don't require vacuuming according to the
***************
*** 500,506 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  		bool		tupgone,
  					hastup;
  		int			prev_dead_count;
- 		OffsetNumber frozen[MaxOffsetNumber];
  		int			nfrozen;
  		Size		freespace;
  		bool		all_visible_according_to_vm;
--- 502,507 ----
***************
*** 890,898 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  				 * Each non-removable tuple must be checked to see if it needs
  				 * freezing.  Note we already have exclusive buffer lock.
  				 */
! 				if (heap_freeze_tuple(tuple.t_data, FreezeLimit,
! 									  MultiXactCutoff))
! 					frozen[nfrozen++] = offnum;
  			}
  		}						/* scan along page */
  
--- 891,899 ----
  				 * Each non-removable tuple must be checked to see if it needs
  				 * freezing.  Note we already have exclusive buffer lock.
  				 */
! 				if (heap_prepare_freeze_tuple(tuple.t_data, FreezeLimit,
! 										  MultiXactCutoff, &frozen[nfrozen]))
! 					frozen[nfrozen++].offset = offnum;
  			}
  		}						/* scan along page */
  
***************
*** 903,917 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  		 */
  		if (nfrozen > 0)
  		{
  			MarkBufferDirty(buf);
  			if (RelationNeedsWAL(onerel))
  			{
  				XLogRecPtr	recptr;
  
  				recptr = log_heap_freeze(onerel, buf, FreezeLimit,
! 										 MultiXactCutoff, frozen, nfrozen);
  				PageSetLSN(page, recptr);
  			}
  		}
  
  		/*
--- 904,936 ----
  		 */
  		if (nfrozen > 0)
  		{
+ 			START_CRIT_SECTION();
+ 
  			MarkBufferDirty(buf);
+ 
+ 			/* execute collected freezes */
+ 			for (i = 0; i < nfrozen; i++)
+ 			{
+ 				ItemId		itemid;
+ 				HeapTupleHeader htup;
+ 
+ 				itemid = PageGetItemId(page, frozen[i].offset);
+ 				htup = (HeapTupleHeader) PageGetItem(page, itemid);
+ 
+ 				heap_execute_freeze_tuple(htup, &frozen[i]);
+ 			}
+ 
+ 			/* Now WAL-log freezing if neccessary */
  			if (RelationNeedsWAL(onerel))
  			{
  				XLogRecPtr	recptr;
  
  				recptr = log_heap_freeze(onerel, buf, FreezeLimit,
! 										 frozen, nfrozen);
  				PageSetLSN(page, recptr);
  			}
+ 
+ 			END_CRIT_SECTION();
  		}
  
  		/*
***************
*** 1012,1017 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 1031,1038 ----
  			RecordPageWithFreeSpace(onerel, blkno, freespace);
  	}
  
+ 	pfree(frozen);
+ 
  	/* save stats for use later */
  	vacrelstats->scanned_tuples = num_tuples;
  	vacrelstats->tuples_deleted = tups_vacuumed;
*** a/src/include/access/heapam_xlog.h
--- b/src/include/access/heapam_xlog.h
***************
*** 48,56 ****
   * the ones above associated with RM_HEAP_ID.  XLOG_HEAP_OPMASK applies to
   * these, too.
   */
! #define XLOG_HEAP2_FREEZE		0x00
  #define XLOG_HEAP2_CLEAN		0x10
! /* 0x20 is free, was XLOG_HEAP2_CLEAN_MOVE */
  #define XLOG_HEAP2_CLEANUP_INFO 0x30
  #define XLOG_HEAP2_VISIBLE		0x40
  #define XLOG_HEAP2_MULTI_INSERT 0x50
--- 48,56 ----
   * the ones above associated with RM_HEAP_ID.  XLOG_HEAP_OPMASK applies to
   * these, too.
   */
! /* 0x00 is free, was XLOG_HEAP2_FREEZE */
  #define XLOG_HEAP2_CLEAN		0x10
! #define XLOG_HEAP2_FREEZE_PAGE	0x20
  #define XLOG_HEAP2_CLEANUP_INFO 0x30
  #define XLOG_HEAP2_VISIBLE		0x40
  #define XLOG_HEAP2_MULTI_INSERT 0x50
***************
*** 270,286 **** typedef struct xl_heap_inplace
  
  #define SizeOfHeapInplace	(offsetof(xl_heap_inplace, target) + SizeOfHeapTid)
  
! /* This is what we need to know about tuple freezing during vacuum */
! typedef struct xl_heap_freeze
  {
  	RelFileNode node;
  	BlockNumber block;
  	TransactionId cutoff_xid;
! 	MultiXactId cutoff_multi;
! 	/* TUPLE OFFSET NUMBERS FOLLOW AT THE END */
! } xl_heap_freeze;
  
! #define SizeOfHeapFreeze (offsetof(xl_heap_freeze, cutoff_multi) + sizeof(MultiXactId))
  
  /* This is what we need to know about setting a visibility map bit */
  typedef struct xl_heap_visible
--- 270,305 ----
  
  #define SizeOfHeapInplace	(offsetof(xl_heap_inplace, target) + SizeOfHeapTid)
  
! /*
!  * a 'freeze plan' struct that represents what we need to know about a single
!  * tuple being frozen during vacuum
!  */
! #define		XLH_FREEZE_XMIN		0x01
! #define		XLH_FREEZE_XVAC		0x02
! #define		XLH_INVALID_XVAC	0x04
! 
! typedef struct xl_heap_freeze_tuple
! {
! 	TransactionId xmax;
! 	OffsetNumber offset;
! 	uint16		t_infomask2;
! 	uint16		t_infomask;
! 	uint8		frzflags;
! } xl_heap_freeze_tuple;
! 
! /*
!  * This is what we need to know about a block being frozen during vacuum
!  */
! typedef struct xl_heap_freeze_page
  {
  	RelFileNode node;
  	BlockNumber block;
  	TransactionId cutoff_xid;
! 	uint16		ntuples;
! 	xl_heap_freeze_tuple tuples[FLEXIBLE_ARRAY_MEMBER];
! } xl_heap_freeze_page;
  
! #define SizeOfHeapFreezePage offsetof(xl_heap_freeze_page, tuples)
  
  /* This is what we need to know about setting a visibility map bit */
  typedef struct xl_heap_visible
***************
*** 331,338 **** extern XLogRecPtr log_heap_clean(Relation reln, Buffer buffer,
  			   OffsetNumber *nowunused, int nunused,
  			   TransactionId latestRemovedXid);
  extern XLogRecPtr log_heap_freeze(Relation reln, Buffer buffer,
! 				TransactionId cutoff_xid, MultiXactId cutoff_multi,
! 				OffsetNumber *offsets, int offcnt);
  extern XLogRecPtr log_heap_visible(RelFileNode rnode, Buffer heap_buffer,
  				 Buffer vm_buffer, TransactionId cutoff_xid);
  extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
--- 350,363 ----
  			   OffsetNumber *nowunused, int nunused,
  			   TransactionId latestRemovedXid);
  extern XLogRecPtr log_heap_freeze(Relation reln, Buffer buffer,
! 				TransactionId cutoff_xid, xl_heap_freeze_tuple *tuples,
! 				int ntuples);
! extern bool heap_prepare_freeze_tuple(HeapTupleHeader tuple,
! 						  TransactionId cutoff_xid,
! 						  TransactionId cutoff_multi,
! 						  xl_heap_freeze_tuple *frz);
! extern void heap_execute_freeze_tuple(HeapTupleHeader tuple,
! 						  xl_heap_freeze_tuple *xlrec_tp);
  extern XLogRecPtr log_heap_visible(RelFileNode rnode, Buffer heap_buffer,
  				 Buffer vm_buffer, TransactionId cutoff_xid);
  extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
*** a/src/include/access/multixact.h
--- b/src/include/access/multixact.h
***************
*** 81,86 **** extern MultiXactId MultiXactIdCreate(TransactionId xid1,
--- 81,89 ----
  				  MultiXactStatus status2);
  extern MultiXactId MultiXactIdExpand(MultiXactId multi, TransactionId xid,
  				  MultiXactStatus status);
+ extern MultiXactId MultiXactIdCreateFromMembers(int nmembers,
+ 							 MultiXactMember *members);
+ 
  extern MultiXactId ReadNextMultiXactId(void);
  extern bool MultiXactIdIsRunning(MultiXactId multi);
  extern void MultiXactIdSetOldestMember(void);
*** a/src/include/access/xlog_internal.h
--- b/src/include/access/xlog_internal.h
***************
*** 55,61 **** typedef struct BkpBlock
  /*
   * Each page of XLOG file has a header like this:
   */
! #define XLOG_PAGE_MAGIC 0xD079	/* can be used as WAL version indicator */
  
  typedef struct XLogPageHeaderData
  {
--- 55,61 ----
  /*
   * Each page of XLOG file has a header like this:
   */
! #define XLOG_PAGE_MAGIC 0xD07A	/* can be used as WAL version indicator */
  
  typedef struct XLogPageHeaderData
  {

>From d266b3cef8598c3383d3ba17105d17fc1f384f7d Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Tue, 10 Dec 2013 17:56:02 -0300
Subject: [PATCH 1/4] Fix freezing of multixacts
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Andres Freund and Álvaro
---
 src/backend/access/heap/heapam.c       |  679 +++++++++++++++++++++++++-------
 src/backend/access/rmgrdesc/heapdesc.c |    9 +
 src/backend/access/transam/multixact.c |   18 +-
 src/backend/commands/vacuumlazy.c      |   31 +-
 src/include/access/heapam_xlog.h       |   43 +-
 src/include/access/multixact.h         |    3 +
 6 files changed, 628 insertions(+), 155 deletions(-)

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 1a0dd21..24d843a 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -5238,14 +5238,261 @@ heap_inplace_update(Relation relation, HeapTuple tuple)
 		CacheInvalidateHeapTuple(relation, tuple, NULL);
 }
 
+#define		FRM_NOOP				0x0001
+#define		FRM_INVALIDATE_XMAX		0x0002
+#define		FRM_RETURN_IS_XID		0x0004
+#define		FRM_RETURN_IS_MULTI		0x0008
+#define		FRM_MARK_COMMITTED		0x0010
 
 /*
- * heap_freeze_tuple
+ * FreezeMultiXactId
+ *		Determine what to do during freezing when a tuple is marked by a
+ *		MultiXactId.
+ *
+ * NB -- this might have the side-effect of creating a new MultiXactId!
+ *
+ * "flags" is an output value; it's used to tell caller what to do on return.
+ * Possible flags are:
+ * FRM_NOOP
+ *		don't do anything -- keep existing Xmax
+ * FRM_INVALIDATE_XMAX
+ *		mark Xmax as InvalidTransactionId and set XMAX_INVALID flag.
+ * FRM_RETURN_IS_XID
+ *		The Xid return value is a single update Xid to set as xmax.
+ * FRM_MARK_COMMITTED
+ *		Xmax can be marked as HEAP_XMAX_COMMITTED
+ * FRM_RETURN_IS_MULTI
+ *		The return value is a new MultiXactId to set as new Xmax.
+ *		(caller must obtain proper infomask bits using GetMultiXactIdHintBits)
+ */
+static TransactionId
+FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
+				  TransactionId cutoff_xid, MultiXactId cutoff_multi,
+				  uint16 *flags)
+{
+	TransactionId xid = InvalidTransactionId;
+	int			i;
+	MultiXactMember *members;
+	int			nmembers;
+	bool		need_replace;
+	int			nnewmembers;
+	MultiXactMember *newmembers;
+	bool		has_lockers;
+	TransactionId update_xid;
+	bool		update_committed;
+
+	*flags = 0;
+
+	/* We should only be called in Multis */
+	Assert(t_infomask & HEAP_XMAX_IS_MULTI);
+
+	if (!MultiXactIdIsValid(multi))
+	{
+		/* Ensure infomask bits are appropriately set/reset */
+		*flags |= FRM_INVALIDATE_XMAX;
+		return InvalidTransactionId;
+	}
+	else if (MultiXactIdPrecedes(multi, cutoff_multi))
+	{
+		/*
+		 * This old multi cannot possibly have members still running.  If it
+		 * was a locker only, it can be removed without any further
+		 * consideration; but if it contained an update, we might need to
+		 * preserve it.
+		 */
+		Assert(!MultiXactIdIsRunning(multi));
+		if (HEAP_XMAX_IS_LOCKED_ONLY(t_infomask))
+		{
+			*flags |= FRM_INVALIDATE_XMAX;
+			xid = InvalidTransactionId; /* not strictly necessary */
+		}
+		else
+		{
+			/* replace multi by update xid */
+			xid = MultiXactIdGetUpdateXid(multi, t_infomask);
+
+			/* wasn't only a lock, xid needs to be valid */
+			Assert(TransactionIdIsValid(xid));
+
+			/*
+			 * If the xid is older than the cutoff, it has to have aborted,
+			 * otherwise the tuple would have gotten pruned away.
+			 */
+			if (TransactionIdPrecedes(xid, cutoff_xid))
+			{
+				Assert(!TransactionIdDidCommit(xid));
+				*flags |= FRM_INVALIDATE_XMAX;
+				xid = InvalidTransactionId;		/* not strictly necessary */
+			}
+			else
+				*flags |= FRM_RETURN_IS_XID;
+		}
+
+		return xid;
+	}
+
+	/*
+	 * This multixact might have or might not have members still running, but
+	 * we know it's valid and is newer than the cutoff point for multis.
+	 * However, some member(s) of it may be below the cutoff for Xids, so we
+	 * need to walk the whole members array to figure out what to do, if
+	 * anything.
+	 */
+
+	nmembers = GetMultiXactIdMembers(multi, &members, false);
+	if (nmembers <= 0)
+	{
+		/* Nothing worth keeping */
+		*flags |= FRM_INVALIDATE_XMAX;
+		return InvalidTransactionId;
+	}
+
+	/* is there anything older than the cutoff? */
+	need_replace = false;
+	for (i = 0; i < nmembers; i++)
+	{
+		if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
+		{
+			need_replace = true;
+			break;
+		}
+	}
+
+	/*
+	 * In the simplest case, there is no member older than the cutoff; we can
+	 * keep the existing MultiXactId as is.
+	 */
+	if (!need_replace)
+	{
+		*flags |= FRM_NOOP;
+		pfree(members);
+		return InvalidTransactionId;
+	}
+
+	/*
+	 * If the multi needs to be updated, figure out which members do we need
+	 * to keep.
+	 */
+	nnewmembers = 0;
+	newmembers = palloc(sizeof(MultiXactMember) * nmembers);
+	has_lockers = false;
+	update_xid = InvalidTransactionId;
+	update_committed = false;
+
+	for (i = 0; i < nmembers; i++)
+	{
+		if (ISUPDATE_from_mxstatus(members[i].status))
+		{
+			/*
+			 * It's an update; should we keep it?  If the transaction is known
+			 * aborted then it's okay to ignore it, otherwise not.  (Note this
+			 * is just an optimization and not needed for correctness, so it's
+			 * okay to get this test wrong; for example, in case an updater is
+			 * crashed, or a running transaction in the process of aborting.)
+			 */
+			if (!TransactionIdDidAbort(members[i].xid))
+			{
+				newmembers[nnewmembers++] = members[i];
+				Assert(!TransactionIdIsValid(update_xid));
+
+				/*
+				 * Tell caller to set HEAP_XMAX_COMMITTED hint while we have
+				 * the Xid in cache.  Again, this is just an optimization, so
+				 * it's not a problem if the transaction is still running and
+				 * in the process of committing.
+				 */
+				if (TransactionIdDidCommit(update_xid))
+					update_committed = true;
+
+				update_xid = newmembers[i].xid;
+			}
+
+			/*
+			 * Checking for very old update Xids is critical: if the update
+			 * member of the multi is older than cutoff_xid, we must remove
+			 * it, because otherwise a later liveliness check could attempt
+			 * pg_clog access for a page that was truncated away by the
+			 * current vacuum.	Note that if the update had committed, we
+			 * wouldn't be freezing this tuple because it would have gotten
+			 * removed (HEAPTUPLE_DEAD) by HeapTupleSatisfiesVacuum; so it
+			 * either aborted or crashed.  Therefore, ignore this update_xid.
+			 */
+			if (TransactionIdPrecedes(update_xid, cutoff_xid))
+			{
+				update_xid = InvalidTransactionId;
+				update_committed = false;
+
+			}
+		}
+		else
+		{
+			/* We only keep lockers if they are still running */
+			if (TransactionIdIsCurrentTransactionId(members[i].xid) ||
+				TransactionIdIsInProgress(members[i].xid))
+			{
+				/* running locker cannot possibly be older than the cutoff */
+				Assert(!TransactionIdPrecedes(members[i].xid, cutoff_xid));
+				newmembers[nnewmembers++] = members[i];
+				has_lockers = true;
+			}
+		}
+	}
+
+	pfree(members);
+
+	if (nnewmembers == 0)
+	{
+		/* nothing worth keeping!? Tell caller to remove the whole thing */
+		*flags |= FRM_INVALIDATE_XMAX;
+		xid = InvalidTransactionId;
+	}
+	else if (TransactionIdIsValid(update_xid) && !has_lockers)
+	{
+		/*
+		 * If there's a single member and it's an update, pass it back alone
+		 * without creating a new Multi.  (XXX we could do this when there's a
+		 * single remaining locker, too, but that would complicate the API too
+		 * much; moreover, the case with the single updater is more
+		 * interesting, because those are longer-lived.)
+		 */
+		Assert(nnewmembers == 1);
+		*flags |= FRM_RETURN_IS_XID;
+		if (update_committed)
+			*flags |= FRM_MARK_COMMITTED;
+		xid = update_xid;
+	}
+	else
+	{
+		/*
+		 * Create a new multixact with the surviving members of the previous
+		 * one, to set as new Xmax in the tuple.
+		 *
+		 * If this is the first possibly-multixact-able operation in the
+		 * current transaction, set my per-backend OldestMemberMXactId
+		 * setting. We can be certain that the transaction will never become a
+		 * member of any older MultiXactIds than that.
+		 */
+		MultiXactIdSetOldestMember();
+		xid = MultiXactIdCreateFromMembers(nnewmembers, newmembers);
+		*flags |= FRM_RETURN_IS_MULTI;
+	}
+
+	pfree(newmembers);
+
+	return xid;
+}
+
+/*
+ * heap_prepare_freeze_tuple
  *
  * Check to see whether any of the XID fields of a tuple (xmin, xmax, xvac)
- * are older than the specified cutoff XID.  If so, replace them with
- * FrozenTransactionId or InvalidTransactionId as appropriate, and return
- * TRUE.  Return FALSE if nothing was changed.
+ * are older than the specified cutoff XID and cutoff MultiXactId.	If so,
+ * setup enough state (in the *frz output argument) to later execute and
+ * WAL-log what we would need to do, and return TRUE.  Return FALSE if nothing
+ * is to be changed.
+ *
+ * Caller is responsible for setting the offset field, if appropriate.	This
+ * is only necessary if the freeze is to be WAL-logged.
  *
  * It is assumed that the caller has checked the tuple with
  * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
@@ -5254,54 +5501,44 @@ heap_inplace_update(Relation relation, HeapTuple tuple)
  * NB: cutoff_xid *must* be <= the current global xmin, to ensure that any
  * XID older than it could neither be running nor seen as running by any
  * open transaction.  This ensures that the replacement will not change
- * anyone's idea of the tuple state.  Also, since we assume the tuple is
- * not HEAPTUPLE_DEAD, the fact that an XID is not still running allows us
- * to assume that it is either committed good or aborted, as appropriate;
- * so we need no external state checks to decide what to do.  (This is good
- * because this function is applied during WAL recovery, when we don't have
- * access to any such state, and can't depend on the hint bits to be set.)
- * There is an exception we make which is to assume GetMultiXactIdMembers can
- * be called during recovery.
- *
+ * anyone's idea of the tuple state.
  * Similarly, cutoff_multi must be less than or equal to the smallest
  * MultiXactId used by any transaction currently open.
  *
  * If the tuple is in a shared buffer, caller must hold an exclusive lock on
  * that buffer.
  *
- * Note: it might seem we could make the changes without exclusive lock, since
- * TransactionId read/write is assumed atomic anyway.  However there is a race
- * condition: someone who just fetched an old XID that we overwrite here could
- * conceivably not finish checking the XID against pg_clog before we finish
- * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
- * exclusive lock ensures no other backend is in process of checking the
- * tuple status.  Also, getting exclusive lock makes it safe to adjust the
- * infomask bits.
- *
- * NB: Cannot rely on hint bits here, they might not be set after a crash or
- * on a standby.
+ * NB: It is not enough to set hint bits to indicate something is
+ * committed/invalid -- they might not be set on a standby, or after crash
+ * recovery.  We really need to remove old xids.
  */
 bool
-heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
-				  MultiXactId cutoff_multi)
+heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+						  TransactionId cutoff_multi,
+						  xl_heap_freeze_tuple *frz)
+
 {
 	bool		changed = false;
 	bool		freeze_xmax = false;
 	TransactionId xid;
 
+	frz->frzflags = 0;
+	frz->t_infomask2 = tuple->t_infomask2;
+	frz->t_infomask = tuple->t_infomask;
+	frz->xmax = HeapTupleHeaderGetRawXmax(tuple);
+
 	/* Process xmin */
 	xid = HeapTupleHeaderGetXmin(tuple);
 	if (TransactionIdIsNormal(xid) &&
 		TransactionIdPrecedes(xid, cutoff_xid))
 	{
-		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+		frz->frzflags |= XLH_FREEZE_XMIN;
 
 		/*
 		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
 		 * already be set here, but there's a small chance not.
 		 */
-		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
-		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+		frz->t_infomask |= HEAP_XMIN_COMMITTED;
 		changed = true;
 	}
 
@@ -5318,91 +5555,35 @@ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 
 	if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
 	{
-		if (!MultiXactIdIsValid(xid))
-		{
-			/* no xmax set, ignore */
-			;
-		}
-		else if (MultiXactIdPrecedes(xid, cutoff_multi))
-		{
-			/*
-			 * This old multi cannot possibly be running.  If it was a locker
-			 * only, it can be removed without much further thought; but if it
-			 * contained an update, we need to preserve it.
-			 */
-			if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
-				freeze_xmax = true;
-			else
-			{
-				TransactionId update_xid;
+		TransactionId newxmax;
+		uint16		flags;
 
-				update_xid = HeapTupleGetUpdateXid(tuple);
-
-				/*
-				 * The multixact has an update hidden within.  Get rid of it.
-				 *
-				 * If the update_xid is below the cutoff_xid, it necessarily
-				 * must be an aborted transaction.  In a primary server, such
-				 * an Xmax would have gotten marked invalid by
-				 * HeapTupleSatisfiesVacuum, but in a replica that is not
-				 * called before we are, so deal with it in the same way.
-				 *
-				 * If not below the cutoff_xid, then the tuple would have been
-				 * pruned by vacuum, if the update committed long enough ago,
-				 * and we wouldn't be freezing it; so it's either recently
-				 * committed, or in-progress.  Deal with this by setting the
-				 * Xmax to the update Xid directly and remove the IS_MULTI
-				 * bit.  (We know there cannot be running lockers in this
-				 * multi, because it's below the cutoff_multi value.)
-				 */
+		newxmax = FreezeMultiXactId(xid, tuple->t_infomask,
+									cutoff_xid, cutoff_multi, &flags);
 
-				if (TransactionIdPrecedes(update_xid, cutoff_xid))
-				{
-					Assert(InRecovery || TransactionIdDidAbort(update_xid));
-					freeze_xmax = true;
-				}
-				else
-				{
-					Assert(InRecovery || !TransactionIdIsInProgress(update_xid));
-					tuple->t_infomask &= ~HEAP_XMAX_BITS;
-					HeapTupleHeaderSetXmax(tuple, update_xid);
-					changed = true;
-				}
-			}
+		if (flags & FRM_INVALIDATE_XMAX)
+			freeze_xmax = true;
+		else if (flags & FRM_RETURN_IS_XID)
+		{
+			frz->t_infomask &= ~HEAP_XMAX_BITS;
+			frz->xmax = newxmax;
+			if (flags & FRM_MARK_COMMITTED)
+				frz->t_infomask &= HEAP_XMAX_COMMITTED;
+			changed = true;
 		}
-		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
+		else if (flags & FRM_RETURN_IS_MULTI)
 		{
-			/* newer than the cutoff, so don't touch it */
-			;
+			frz->t_infomask &= ~HEAP_XMAX_BITS;
+			frz->xmax = newxmax;
+
+			GetMultiXactIdHintBits(newxmax,
+								   &frz->t_infomask,
+								   &frz->t_infomask2);
+			changed = true;
 		}
 		else
 		{
-			TransactionId	update_xid;
-
-			/*
-			 * This is a multixact which is not marked LOCK_ONLY, but which
-			 * is newer than the cutoff_multi.  If the update_xid is below the
-			 * cutoff_xid point, then we can just freeze the Xmax in the
-			 * tuple, removing it altogether.  This seems simple, but there
-			 * are several underlying assumptions:
-			 *
-			 * 1. A tuple marked by an multixact containing a very old
-			 * committed update Xid would have been pruned away by vacuum; we
-			 * wouldn't be freezing this tuple at all.
-			 *
-			 * 2. There cannot possibly be any live locking members remaining
-			 * in the multixact.  This is because if they were alive, the
-			 * update's Xid would had been considered, via the lockers'
-			 * snapshot's Xmin, as part the cutoff_xid.
-			 *
-			 * 3. We don't create new MultiXacts via MultiXactIdExpand() that
-			 * include a very old aborted update Xid: in that function we only
-			 * include update Xids corresponding to transactions that are
-			 * committed or in-progress.
-			 */
-			update_xid = HeapTupleGetUpdateXid(tuple);
-			if (TransactionIdPrecedes(update_xid, cutoff_xid))
-				freeze_xmax = true;
+			Assert(flags & FRM_NOOP);
 		}
 	}
 	else if (TransactionIdIsNormal(xid) &&
@@ -5413,17 +5594,17 @@ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 
 	if (freeze_xmax)
 	{
-		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
+		frz->xmax = InvalidTransactionId;
 
 		/*
 		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
 		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
 		 * Also get rid of the HEAP_KEYS_UPDATED bit.
 		 */
-		tuple->t_infomask &= ~HEAP_XMAX_BITS;
-		tuple->t_infomask |= HEAP_XMAX_INVALID;
-		HeapTupleHeaderClearHotUpdated(tuple);
-		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
+		frz->t_infomask &= ~HEAP_XMAX_BITS;
+		frz->t_infomask |= HEAP_XMAX_INVALID;
+		frz->t_infomask2 &= ~HEAP_HOT_UPDATED;
+		frz->t_infomask2 &= ~HEAP_KEYS_UPDATED;
 		changed = true;
 	}
 
@@ -5443,16 +5624,16 @@ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 			 * xvac transaction succeeded.
 			 */
 			if (tuple->t_infomask & HEAP_MOVED_OFF)
-				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+				frz->frzflags |= XLH_INVALID_XVAC;
 			else
-				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+				frz->frzflags |= XLH_FREEZE_XVAC;
 
 			/*
 			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
 			 * will already be set here, but there's a small chance not.
 			 */
 			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
-			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+			frz->t_infomask |= HEAP_XMIN_COMMITTED;
 			changed = true;
 		}
 	}
@@ -5461,6 +5642,68 @@ heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 }
 
 /*
+ * heap_execute_freeze_tuple
+ *		Execute the prepared freezing of a tuple.
+ *
+ * Caller is responsible for ensuring that no other backend can access the
+ * storage underlying this tuple, either by holding an exclusive lock on the
+ * buffer containing it (which is what lazy VACUUM does), or by having it by
+ * in private storage (which is what CLUSTER and friends do).
+ *
+ * Note: it might seem we could make the changes without exclusive lock, since
+ * TransactionId read/write is assumed atomic anyway.  However there is a race
+ * condition: someone who just fetched an old XID that we overwrite here could
+ * conceivably not finish checking the XID against pg_clog before we finish
+ * the VACUUM and perhaps truncate off the part of pg_clog he needs.  Getting
+ * exclusive lock ensures no other backend is in process of checking the
+ * tuple status.  Also, getting exclusive lock makes it safe to adjust the
+ * infomask bits.
+ *
+ * NB: All code in here must be safe to execute during crash recovery!
+ */
+void
+heap_execute_freeze_tuple(HeapTupleHeader tuple, xl_heap_freeze_tuple *frz)
+{
+	if (frz->frzflags & XLH_FREEZE_XMIN)
+		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+
+	HeapTupleHeaderSetXmax(tuple, frz->xmax);
+
+	if (frz->frzflags & XLH_FREEZE_XVAC)
+		HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+
+	if (frz->frzflags & XLH_INVALID_XVAC)
+		HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+
+	tuple->t_infomask = frz->t_infomask;
+	tuple->t_infomask2 = frz->t_infomask2;
+}
+
+/*
+ * heap_freeze_tuple - freeze tuple inplace without WAL logging.
+ *
+ * Useful for callers like CLUSTER that perform their own WAL logging.
+ */
+bool
+heap_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+				  TransactionId cutoff_multi)
+{
+	xl_heap_freeze_tuple frz;
+	bool		do_freeze;
+
+	do_freeze = heap_prepare_freeze_tuple(tuple, cutoff_xid, cutoff_multi, &frz);
+
+	/*
+	 * Note that because this is not a WAL-logged operation, we don't need to
+	 * fill in the offset in the freeze record.
+	 */
+
+	if (do_freeze)
+		heap_execute_freeze_tuple(tuple, &frz);
+	return do_freeze;
+}
+
+/*
  * For a given MultiXactId, return the hint bits that should be set in the
  * tuple's infomask.
  *
@@ -5763,16 +6006,26 @@ heap_tuple_needs_freeze(HeapTupleHeader tuple, TransactionId cutoff_xid,
 		}
 		else if (MultiXactIdPrecedes(multi, cutoff_multi))
 			return true;
-		else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
-		{
-			/* only-locker multis don't need internal examination */
-			;
-		}
 		else
 		{
-			if (TransactionIdPrecedes(HeapTupleGetUpdateXid(tuple),
-									  cutoff_xid))
-				return true;
+			MultiXactMember *members;
+			int			nmembers;
+			int			i;
+
+			/* need to check whether any member of the mxact is too old */
+
+			nmembers = GetMultiXactIdMembers(multi, &members, false);
+
+			for (i = 0; i < nmembers; i++)
+			{
+				if (TransactionIdPrecedes(members[i].xid, cutoff_xid))
+				{
+					pfree(members);
+					return true;
+				}
+			}
+			if (nmembers > 0)
+				pfree(members);
 		}
 	}
 	else
@@ -6022,27 +6275,26 @@ log_heap_clean(Relation reln, Buffer buffer,
 }
 
 /*
- * Perform XLogInsert for a heap-freeze operation.	Caller must already
- * have modified the buffer and marked it dirty.
+ * Perform XLogInsert for a heap-freeze operation.	Caller must have already
+ * modified the buffer and marked it dirty.
  */
 XLogRecPtr
-log_heap_freeze(Relation reln, Buffer buffer,
-				TransactionId cutoff_xid, MultiXactId cutoff_multi,
-				OffsetNumber *offsets, int offcnt)
+log_heap_freeze(Relation reln, Buffer buffer, TransactionId cutoff_xid,
+				xl_heap_freeze_tuple *tuples, int ntuples)
 {
-	xl_heap_freeze xlrec;
+	xl_heap_freeze_page xlrec;
 	XLogRecPtr	recptr;
 	XLogRecData rdata[2];
 
 	/* Caller should not call me on a non-WAL-logged relation */
 	Assert(RelationNeedsWAL(reln));
 	/* nor when there are no tuples to freeze */
-	Assert(offcnt > 0);
+	Assert(ntuples > 0);
 
 	xlrec.node = reln->rd_node;
 	xlrec.block = BufferGetBlockNumber(buffer);
 	xlrec.cutoff_xid = cutoff_xid;
-	xlrec.cutoff_multi = cutoff_multi;
+	xlrec.ntuples = ntuples;
 
 	rdata[0].data = (char *) &xlrec;
 	rdata[0].len = SizeOfHeapFreeze;
@@ -6050,17 +6302,17 @@ log_heap_freeze(Relation reln, Buffer buffer,
 	rdata[0].next = &(rdata[1]);
 
 	/*
-	 * The tuple-offsets array is not actually in the buffer, but pretend that
-	 * it is.  When XLogInsert stores the whole buffer, the offsets array need
+	 * The freeze plan array is not actually in the buffer, but pretend that
+	 * it is.  When XLogInsert stores the whole buffer, the freeze plan need
 	 * not be stored too.
 	 */
-	rdata[1].data = (char *) offsets;
-	rdata[1].len = offcnt * sizeof(OffsetNumber);
+	rdata[1].data = (char *) tuples;
+	rdata[1].len = ntuples * sizeof(xl_heap_freeze_tuple);
 	rdata[1].buffer = buffer;
 	rdata[1].buffer_std = true;
 	rdata[1].next = NULL;
 
-	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE, rdata);
+	recptr = XLogInsert(RM_HEAP2_ID, XLOG_HEAP2_FREEZE_PAGE, rdata);
 
 	return recptr;
 }
@@ -6402,6 +6654,99 @@ heap_xlog_clean(XLogRecPtr lsn, XLogRecord *record)
 	XLogRecordPageWithFreeSpace(xlrec->node, xlrec->block, freespace);
 }
 
+/*
+ * Freeze a single tuple for XLOG_HEAP2_FREEZE
+ *
+ * NB: This type of record aren't generated anymore, since bugs around
+ * multixacts couldn't be fixed without a more robust type of freezing. This
+ * is kept around to be able to perform PITR.
+ */
+static bool
+heap_xlog_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
+					   MultiXactId cutoff_multi)
+{
+	bool		changed = false;
+	TransactionId xid;
+
+	xid = HeapTupleHeaderGetXmin(tuple);
+	if (TransactionIdIsNormal(xid) &&
+		TransactionIdPrecedes(xid, cutoff_xid))
+	{
+		HeapTupleHeaderSetXmin(tuple, FrozenTransactionId);
+
+		/*
+		 * Might as well fix the hint bits too; usually XMIN_COMMITTED will
+		 * already be set here, but there's a small chance not.
+		 */
+		Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
+		tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+		changed = true;
+	}
+
+	/*
+	 * Note that this code handles IS_MULTI Xmax values, too, but only to mark
+	 * the tuple as not updated if the multixact is below the cutoff Multixact
+	 * given; it doesn't remove dead members of a very old multixact.
+	 */
+	xid = HeapTupleHeaderGetRawXmax(tuple);
+	if ((tuple->t_infomask & HEAP_XMAX_IS_MULTI) ?
+		(MultiXactIdIsValid(xid) &&
+		 MultiXactIdPrecedes(xid, cutoff_multi)) :
+		(TransactionIdIsNormal(xid) &&
+		 TransactionIdPrecedes(xid, cutoff_xid)))
+	{
+		HeapTupleHeaderSetXmax(tuple, InvalidTransactionId);
+
+		/*
+		 * The tuple might be marked either XMAX_INVALID or XMAX_COMMITTED +
+		 * LOCKED.	Normalize to INVALID just to be sure no one gets confused.
+		 * Also get rid of the HEAP_KEYS_UPDATED bit.
+		 */
+		tuple->t_infomask &= ~HEAP_XMAX_BITS;
+		tuple->t_infomask |= HEAP_XMAX_INVALID;
+		HeapTupleHeaderClearHotUpdated(tuple);
+		tuple->t_infomask2 &= ~HEAP_KEYS_UPDATED;
+		changed = true;
+	}
+
+	/*
+	 * Old-style VACUUM FULL is gone, but we have to keep this code as long as
+	 * we support having MOVED_OFF/MOVED_IN tuples in the database.
+	 */
+	if (tuple->t_infomask & HEAP_MOVED)
+	{
+		xid = HeapTupleHeaderGetXvac(tuple);
+		if (TransactionIdIsNormal(xid) &&
+			TransactionIdPrecedes(xid, cutoff_xid))
+		{
+			/*
+			 * If a MOVED_OFF tuple is not dead, the xvac transaction must
+			 * have failed; whereas a non-dead MOVED_IN tuple must mean the
+			 * xvac transaction succeeded.
+			 */
+			if (tuple->t_infomask & HEAP_MOVED_OFF)
+				HeapTupleHeaderSetXvac(tuple, InvalidTransactionId);
+			else
+				HeapTupleHeaderSetXvac(tuple, FrozenTransactionId);
+
+			/*
+			 * Might as well fix the hint bits too; usually XMIN_COMMITTED
+			 * will already be set here, but there's a small chance not.
+			 */
+			Assert(!(tuple->t_infomask & HEAP_XMIN_INVALID));
+			tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+			changed = true;
+		}
+	}
+
+	return changed;
+}
+
+/*
+ * NB: This type of record aren't generated anymore, since bugs around
+ * multixacts couldn't be fixed without a more robust type of freezing. This
+ * is kept around to be able to perform PITR.
+ */
 static void
 heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
 {
@@ -6450,7 +6795,7 @@ heap_xlog_freeze(XLogRecPtr lsn, XLogRecord *record)
 			ItemId		lp = PageGetItemId(page, *offsets);
 			HeapTupleHeader tuple = (HeapTupleHeader) PageGetItem(page, lp);
 
-			(void) heap_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
+			(void) heap_xlog_freeze_tuple(tuple, cutoff_xid, cutoff_multi);
 			offsets++;
 		}
 	}
@@ -6574,6 +6919,63 @@ heap_xlog_visible(XLogRecPtr lsn, XLogRecord *record)
 	}
 }
 
+/*
+ * Replay XLOG_HEAP2_FREEZE_PAGE records
+ */
+static void
+heap_xlog_freeze_page(XLogRecPtr lsn, XLogRecord *record)
+{
+	xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) XLogRecGetData(record);
+	TransactionId cutoff_xid = xlrec->cutoff_xid;
+	Buffer		buffer;
+	Page		page;
+	int			ntup;
+
+	/*
+	 * In Hot Standby mode, ensure that there's no queries running which still
+	 * consider the frozen xids as running.
+	 */
+	if (InHotStandby)
+		ResolveRecoveryConflictWithSnapshot(cutoff_xid, xlrec->node);
+
+	/* If we have a full-page image, restore it and we're done */
+	if (record->xl_info & XLR_BKP_BLOCK(0))
+	{
+		(void) RestoreBackupBlock(lsn, record, 0, false, false);
+		return;
+	}
+
+	buffer = XLogReadBuffer(xlrec->node, xlrec->block, false);
+	if (!BufferIsValid(buffer))
+		return;
+
+	page = (Page) BufferGetPage(buffer);
+
+	if (lsn <= PageGetLSN(page))
+	{
+		UnlockReleaseBuffer(buffer);
+		return;
+	}
+
+	/* now execute freeze plan for each frozen tuple */
+	for (ntup = 0; ntup < xlrec->ntuples; ntup++)
+	{
+		xl_heap_freeze_tuple *xlrec_tp;
+		ItemId		lp;
+		HeapTupleHeader tuple;
+
+		xlrec_tp = &xlrec->tuples[ntup];
+		lp = PageGetItemId(page, xlrec_tp->offset);		/* offsets are one-based */
+		tuple = (HeapTupleHeader) PageGetItem(page, lp);
+
+		heap_execute_freeze_tuple(tuple, xlrec_tp);
+	}
+
+	PageSetLSN(page, lsn);
+	MarkBufferDirty(buffer);
+	UnlockReleaseBuffer(buffer);
+}
+
 static void
 heap_xlog_newpage(XLogRecPtr lsn, XLogRecord *record)
 {
@@ -7429,6 +7831,9 @@ heap2_redo(XLogRecPtr lsn, XLogRecord *record)
 		case XLOG_HEAP2_CLEAN:
 			heap_xlog_clean(lsn, record);
 			break;
+		case XLOG_HEAP2_FREEZE_PAGE:
+			heap_xlog_freeze_page(lsn, record);
+			break;
 		case XLOG_HEAP2_CLEANUP_INFO:
 			heap_xlog_cleanup_info(lsn, record);
 			break;
diff --git a/src/backend/access/rmgrdesc/heapdesc.c b/src/backend/access/rmgrdesc/heapdesc.c
index bc8b985..d527aa6 100644
--- a/src/backend/access/rmgrdesc/heapdesc.c
+++ b/src/backend/access/rmgrdesc/heapdesc.c
@@ -149,6 +149,15 @@ heap2_desc(StringInfo buf, uint8 xl_info, char *rec)
 						 xlrec->node.relNode, xlrec->block,
 						 xlrec->latestRemovedXid);
 	}
+	else if (info == XLOG_HEAP2_FREEZE_PAGE)
+	{
+		xl_heap_freeze_page *xlrec = (xl_heap_freeze_page *) rec;
+
+		appendStringInfo(buf, "freeze_page: rel %u/%u/%u; blk %u; cutoff xid %u ntuples %u",
+						 xlrec->node.spcNode, xlrec->node.dbNode,
+						 xlrec->node.relNode, xlrec->block,
+						 xlrec->cutoff_xid, xlrec->ntuples);
+	}
 	else if (info == XLOG_HEAP2_CLEANUP_INFO)
 	{
 		xl_heap_cleanup_info *xlrec = (xl_heap_cleanup_info *) rec;
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 2081470..ed7101f 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -286,7 +286,6 @@ static MemoryContext MXactContext = NULL;
 
 /* internal MultiXactId management */
 static void MultiXactIdSetOldestVisible(void);
-static MultiXactId CreateMultiXactId(int nmembers, MultiXactMember *members);
 static void RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
 				   int nmembers, MultiXactMember *members);
 static MultiXactId GetNewMultiXactId(int nmembers, MultiXactOffset *offset);
@@ -344,7 +343,7 @@ MultiXactIdCreate(TransactionId xid1, MultiXactStatus status1,
 	members[1].xid = xid2;
 	members[1].status = status2;
 
-	newMulti = CreateMultiXactId(2, members);
+	newMulti = MultiXactIdCreateFromMembers(2, members);
 
 	debug_elog3(DEBUG2, "Create: %s",
 				mxid_to_string(newMulti, 2, members));
@@ -407,7 +406,7 @@ MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
 		 */
 		member.xid = xid;
 		member.status = status;
-		newMulti = CreateMultiXactId(1, &member);
+		newMulti = MultiXactIdCreateFromMembers(1, &member);
 
 		debug_elog4(DEBUG2, "Expand: %u has no members, create singleton %u",
 					multi, newMulti);
@@ -459,7 +458,7 @@ MultiXactIdExpand(MultiXactId multi, TransactionId xid, MultiXactStatus status)
 
 	newMembers[j].xid = xid;
 	newMembers[j++].status = status;
-	newMulti = CreateMultiXactId(j, newMembers);
+	newMulti = MultiXactIdCreateFromMembers(j, newMembers);
 
 	pfree(members);
 	pfree(newMembers);
@@ -664,16 +663,16 @@ ReadNextMultiXactId(void)
 }
 
 /*
- * CreateMultiXactId
- *		Make a new MultiXactId
+ * MultiXactIdCreateFromMembers
+ *		Make a new MultiXactId from the specified set of members
  *
  * Make XLOG, SLRU and cache entries for a new MultiXactId, recording the
  * given TransactionIds as members.  Returns the newly created MultiXactId.
  *
  * NB: the passed members[] array will be sorted in-place.
  */
-static MultiXactId
-CreateMultiXactId(int nmembers, MultiXactMember *members)
+MultiXactId
+MultiXactIdCreateFromMembers(int nmembers, MultiXactMember *members)
 {
 	MultiXactId multi;
 	MultiXactOffset offset;
@@ -760,7 +759,8 @@ CreateMultiXactId(int nmembers, MultiXactMember *members)
  * RecordNewMultiXact
  *		Write info about a new multixact into the offsets and members files
  *
- * This is broken out of CreateMultiXactId so that xlog replay can use it.
+ * This is broken out of MultiXactIdCreateFromMembers so that xlog replay can
+ * use it.
  */
 static void
 RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
diff --git a/src/backend/commands/vacuumlazy.c b/src/backend/commands/vacuumlazy.c
index ff6bd8e..01b6f46 100644
--- a/src/backend/commands/vacuumlazy.c
+++ b/src/backend/commands/vacuumlazy.c
@@ -424,6 +424,7 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 	Buffer		vmbuffer = InvalidBuffer;
 	BlockNumber next_not_all_visible_block;
 	bool		skipping_all_visible_blocks;
+	xl_heap_freeze_tuple *frozen;
 
 	pg_rusage_init(&ru0);
 
@@ -446,6 +447,7 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 	vacrelstats->latestRemovedXid = InvalidTransactionId;
 
 	lazy_space_alloc(vacrelstats, nblocks);
+	frozen = palloc(sizeof(xl_heap_freeze_tuple) * MaxHeapTuplesPerPage);
 
 	/*
 	 * We want to skip pages that don't require vacuuming according to the
@@ -500,7 +502,6 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 		bool		tupgone,
 					hastup;
 		int			prev_dead_count;
-		OffsetNumber frozen[MaxOffsetNumber];
 		int			nfrozen;
 		Size		freespace;
 		bool		all_visible_according_to_vm;
@@ -893,9 +894,9 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 				 * Each non-removable tuple must be checked to see if it needs
 				 * freezing.  Note we already have exclusive buffer lock.
 				 */
-				if (heap_freeze_tuple(tuple.t_data, FreezeLimit,
-									  MultiXactCutoff))
-					frozen[nfrozen++] = offnum;
+				if (heap_prepare_freeze_tuple(tuple.t_data, FreezeLimit,
+										  MultiXactCutoff, &frozen[nfrozen]))
+					frozen[nfrozen++].offset = offnum;
 			}
 		}						/* scan along page */
 
@@ -906,15 +907,33 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 		 */
 		if (nfrozen > 0)
 		{
+			START_CRIT_SECTION();
+
 			MarkBufferDirty(buf);
+
+			/* execute collected freezes */
+			for (i = 0; i < nfrozen; i++)
+			{
+				ItemId		itemid;
+				HeapTupleHeader htup;
+
+				itemid = PageGetItemId(page, frozen[i].offset);
+				htup = (HeapTupleHeader) PageGetItem(page, itemid);
+
+				heap_execute_freeze_tuple(htup, &frozen[i]);
+			}
+
+			/* Now WAL-log freezing if neccessary */
 			if (RelationNeedsWAL(onerel))
 			{
 				XLogRecPtr	recptr;
 
 				recptr = log_heap_freeze(onerel, buf, FreezeLimit,
-										 MultiXactCutoff, frozen, nfrozen);
+										 frozen, nfrozen);
 				PageSetLSN(page, recptr);
 			}
+
+			END_CRIT_SECTION();
 		}
 
 		/*
@@ -1015,6 +1034,8 @@ lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
 			RecordPageWithFreeSpace(onerel, blkno, freespace);
 	}
 
+	pfree(frozen);
+
 	/* save stats for use later */
 	vacrelstats->scanned_tuples = num_tuples;
 	vacrelstats->tuples_deleted = tups_vacuumed;
diff --git a/src/include/access/heapam_xlog.h b/src/include/access/heapam_xlog.h
index 4381778..138b879 100644
--- a/src/include/access/heapam_xlog.h
+++ b/src/include/access/heapam_xlog.h
@@ -50,7 +50,7 @@
  */
 #define XLOG_HEAP2_FREEZE		0x00
 #define XLOG_HEAP2_CLEAN		0x10
-/* 0x20 is free, was XLOG_HEAP2_CLEAN_MOVE */
+#define XLOG_HEAP2_FREEZE_PAGE	0x20
 #define XLOG_HEAP2_CLEANUP_INFO 0x30
 #define XLOG_HEAP2_VISIBLE		0x40
 #define XLOG_HEAP2_MULTI_INSERT 0x50
@@ -239,7 +239,7 @@ typedef struct xl_heap_inplace
 
 #define SizeOfHeapInplace	(offsetof(xl_heap_inplace, target) + SizeOfHeapTid)
 
-/* This is what we need to know about tuple freezing during vacuum */
+/* This is what we need to know about tuple freezing during vacuum (legacy) */
 typedef struct xl_heap_freeze
 {
 	RelFileNode node;
@@ -251,6 +251,35 @@ typedef struct xl_heap_freeze
 
 #define SizeOfHeapFreeze (offsetof(xl_heap_freeze, cutoff_multi) + sizeof(MultiXactId))
 
+/*
+ * a 'freeze plan' struct that represents what we need to know about a single
+ * tuple being frozen during vacuum
+ */
+#define		XLH_FREEZE_XMIN		0x01
+#define		XLH_FREEZE_XVAC		0x02
+#define		XLH_INVALID_XVAC	0x04
+
+typedef struct xl_heap_freeze_tuple
+{
+	TransactionId xmax;
+	OffsetNumber offset;
+	uint16		t_infomask2;
+	uint16		t_infomask;
+	uint8		frzflags;
+} xl_heap_freeze_tuple;
+
+/*
+ * This is what we need to know about a block being frozen during vacuum
+ */
+typedef struct xl_heap_freeze_block
+{
+	RelFileNode node;
+	BlockNumber block;
+	TransactionId cutoff_xid;
+	uint16		ntuples;
+	xl_heap_freeze_tuple tuples[FLEXIBLE_ARRAY_MEMBER];
+} xl_heap_freeze_page;
+
 /* This is what we need to know about setting a visibility map bit */
 typedef struct xl_heap_visible
 {
@@ -277,8 +306,14 @@ extern XLogRecPtr log_heap_clean(Relation reln, Buffer buffer,
 			   OffsetNumber *nowunused, int nunused,
 			   TransactionId latestRemovedXid);
 extern XLogRecPtr log_heap_freeze(Relation reln, Buffer buffer,
-				TransactionId cutoff_xid, MultiXactId cutoff_multi,
-				OffsetNumber *offsets, int offcnt);
+				TransactionId cutoff_xid, xl_heap_freeze_tuple *tuples,
+				int ntuples);
+extern bool heap_prepare_freeze_tuple(HeapTupleHeader tuple,
+						  TransactionId cutoff_xid,
+						  TransactionId cutoff_multi,
+						  xl_heap_freeze_tuple *frz);
+extern void heap_execute_freeze_tuple(HeapTupleHeader tuple,
+						  xl_heap_freeze_tuple *xlrec_tp);
 extern XLogRecPtr log_heap_visible(RelFileNode rnode, Buffer heap_buffer,
 				 Buffer vm_buffer, TransactionId cutoff_xid);
 extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
diff --git a/src/include/access/multixact.h b/src/include/access/multixact.h
index 6085ea3..0e3b273 100644
--- a/src/include/access/multixact.h
+++ b/src/include/access/multixact.h
@@ -81,6 +81,9 @@ extern MultiXactId MultiXactIdCreate(TransactionId xid1,
 				  MultiXactStatus status2);
 extern MultiXactId MultiXactIdExpand(MultiXactId multi, TransactionId xid,
 				  MultiXactStatus status);
+extern MultiXactId MultiXactIdCreateFromMembers(int nmembers,
+							 MultiXactMember *members);
+
 extern MultiXactId ReadNextMultiXactId(void);
 extern bool MultiXactIdIsRunning(MultiXactId multi);
 extern void MultiXactIdSetOldestMember(void);
-- 
1.7.10.4

>From 22f88d30be9f9d97febb335599f2235918685278 Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Wed, 11 Dec 2013 13:44:12 -0300
Subject: [PATCH 2/4] fixups for 9.3

---
 src/backend/access/heap/heapam.c |    2 +-
 src/include/access/heapam_xlog.h |    4 +++-
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 24d843a..9509480 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -6297,7 +6297,7 @@ log_heap_freeze(Relation reln, Buffer buffer, TransactionId cutoff_xid,
 	xlrec.ntuples = ntuples;
 
 	rdata[0].data = (char *) &xlrec;
-	rdata[0].len = SizeOfHeapFreeze;
+	rdata[0].len = SizeOfHeapFreezePage;
 	rdata[0].buffer = InvalidBuffer;
 	rdata[0].next = &(rdata[1]);
 
diff --git a/src/include/access/heapam_xlog.h b/src/include/access/heapam_xlog.h
index 138b879..8d25245 100644
--- a/src/include/access/heapam_xlog.h
+++ b/src/include/access/heapam_xlog.h
@@ -271,7 +271,7 @@ typedef struct xl_heap_freeze_tuple
 /*
  * This is what we need to know about a block being frozen during vacuum
  */
-typedef struct xl_heap_freeze_block
+typedef struct xl_heap_freeze_page
 {
 	RelFileNode node;
 	BlockNumber block;
@@ -280,6 +280,8 @@ typedef struct xl_heap_freeze_block
 	xl_heap_freeze_tuple tuples[FLEXIBLE_ARRAY_MEMBER];
 } xl_heap_freeze_page;
 
+#define SizeOfHeapFreezePage offsetof(xl_heap_freeze_page, tuples)
+
 /* This is what we need to know about setting a visibility map bit */
 typedef struct xl_heap_visible
 {
-- 
1.7.10.4

>From 35fdab06ceefcd0b4399550d76f9e134a1ae5880 Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Thu, 12 Dec 2013 17:27:54 -0300
Subject: [PATCH 3/4] fixup XidIsInProgress before transam.c tests

---
 src/backend/access/heap/heapam.c |   81 ++++++++++++++++++++++++++------------
 1 file changed, 55 insertions(+), 26 deletions(-)

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 9509480..9616c18 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -5381,47 +5381,76 @@ FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
 
 	for (i = 0; i < nmembers; i++)
 	{
+		/*
+		 * Determine whether to keep this member or ignore it.
+		 */
 		if (ISUPDATE_from_mxstatus(members[i].status))
 		{
+			TransactionId	xid = members[i].xid;
+
 			/*
 			 * It's an update; should we keep it?  If the transaction is known
-			 * aborted then it's okay to ignore it, otherwise not.  (Note this
-			 * is just an optimization and not needed for correctness, so it's
-			 * okay to get this test wrong; for example, in case an updater is
-			 * crashed, or a running transaction in the process of aborting.)
+			 * aborted then it's okay to ignore it, otherwise not.  However,
+			 * if the Xid is older than the cutoff_xid, we must remove it,
+			 * because otherwise we might allow a very old Xid to persist
+			 * which would later cause pg_clog lookups problems, because the
+			 * corresponding SLRU segment might be about to be truncated away.
+			 * (Note that such an old updater cannot possibly be committed,
+			 * because HeapTupleSatisfiesVacuum would have returned
+			 * HEAPTUPLE_DEAD and we would not be trying to freeze the tuple.)
+			 *
+			 * Note the TransactionIdDidAbort() test is just an optimization
+			 * and not strictly necessary for correctness.
+			 *
+			 * As with all tuple visibility routines, it's critical to test
+			 * TransactionIdIsInProgress before the transam.c routines,
+			 * because of race conditions explained in detail in tqual.c.
 			 */
-			if (!TransactionIdDidAbort(members[i].xid))
+			if (TransactionIdIsCurrentTransactionId(xid) ||
+				TransactionIdIsInProgress(xid))
 			{
-				newmembers[nnewmembers++] = members[i];
 				Assert(!TransactionIdIsValid(update_xid));
-
+				update_xid = xid;
+			}
+			else if (!TransactionIdDidAbort(xid))
+			{
 				/*
-				 * Tell caller to set HEAP_XMAX_COMMITTED hint while we have
-				 * the Xid in cache.  Again, this is just an optimization, so
-				 * it's not a problem if the transaction is still running and
-				 * in the process of committing.
+				 * Test whether to tell caller to set HEAP_XMAX_COMMITTED
+				 * while we have the Xid still in cache.  Note this can only
+				 * be done if the transaction is known not running.
 				 */
-				if (TransactionIdDidCommit(update_xid))
+				if (TransactionIdDidCommit(xid))
 					update_committed = true;
-
-				update_xid = newmembers[i].xid;
+				Assert(!TransactionIdIsValid(update_xid));
+				update_xid = xid;
 			}
 
 			/*
-			 * Checking for very old update Xids is critical: if the update
-			 * member of the multi is older than cutoff_xid, we must remove
-			 * it, because otherwise a later liveliness check could attempt
-			 * pg_clog access for a page that was truncated away by the
-			 * current vacuum.	Note that if the update had committed, we
-			 * wouldn't be freezing this tuple because it would have gotten
-			 * removed (HEAPTUPLE_DEAD) by HeapTupleSatisfiesVacuum; so it
-			 * either aborted or crashed.  Therefore, ignore this update_xid.
+			 * If we determined that it's an Xid corresponding to an update
+			 * that must be retained, additionally add it to the list of
+			 * members of the new Multis, in case we end up using that.  (We
+			 * might still decide to use only an update Xid and not a multi,
+			 * but it's easier to maintain the list as we walk the old members
+			 * list.)
+			 *
+			 * It is possible to end up with a very old updater Xid that
+			 * crashed and thus did not mark itself as aborted in pg_clog.
+			 * That would manifest as a pre-cutoff Xid.  Make sure to ignore
+			 * it.
 			 */
-			if (TransactionIdPrecedes(update_xid, cutoff_xid))
+			if (TransactionIdIsValid(update_xid))
 			{
-				update_xid = InvalidTransactionId;
-				update_committed = false;
-
+				if (!TransactionIdPrecedes(update_xid, cutoff_xid))
+				{
+					newmembers[nnewmembers++] = members[i];
+				}
+				else
+				{
+					/* cannot have committed: would be HEAPTUPLE_DEAD */
+					Assert(!TransactionIdDidCommit(update_xid));
+					update_xid = InvalidTransactionId;
+					update_committed = false;
+				}
 			}
 		}
 		else
-- 
1.7.10.4

>From fdfd992ff907e75d4c1c009b9b191748678d5daf Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Thu, 12 Dec 2013 18:18:36 -0300
Subject: [PATCH 4/4] set the PROC_FREEZING_MULTI flag to avoid assert

---
 src/backend/access/heap/heapam.c       |   20 ++++++++++++++++----
 src/backend/access/transam/multixact.c |    9 +++++++--
 src/include/storage/proc.h             |    3 ++-
 3 files changed, 25 insertions(+), 7 deletions(-)

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 9616c18..bf9300d 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -60,6 +60,7 @@
 #include "storage/freespace.h"
 #include "storage/lmgr.h"
 #include "storage/predicate.h"
+#include "storage/proc.h"
 #include "storage/procarray.h"
 #include "storage/smgr.h"
 #include "storage/standby.h"
@@ -5520,8 +5521,7 @@ FreezeMultiXactId(MultiXactId multi, uint16 t_infomask,
  * WAL-log what we would need to do, and return TRUE.  Return FALSE if nothing
  * is to be changed.
  *
- * Caller is responsible for setting the offset field, if appropriate.	This
- * is only necessary if the freeze is to be WAL-logged.
+ * Caller is responsible for setting the offset field, if appropriate.
  *
  * It is assumed that the caller has checked the tuple with
  * HeapTupleSatisfiesVacuum() and determined that it is not HEAPTUPLE_DEAD
@@ -5587,8 +5587,20 @@ heap_prepare_freeze_tuple(HeapTupleHeader tuple, TransactionId cutoff_xid,
 		TransactionId newxmax;
 		uint16		flags;
 
-		newxmax = FreezeMultiXactId(xid, tuple->t_infomask,
-									cutoff_xid, cutoff_multi, &flags);
+		PG_TRY();
+		{
+			/* set flag to let multixact.c know what we're doing */
+			MyPgXact->vacuumFlags |= PROC_FREEZING_MULTI;
+			newxmax = FreezeMultiXactId(xid, tuple->t_infomask,
+										cutoff_xid, cutoff_multi, &flags);
+		}
+		PG_CATCH();
+		{
+			MyPgXact->vacuumFlags &= ~PROC_FREEZING_MULTI;
+			PG_RE_THROW();
+		}
+		PG_END_TRY();
+		MyPgXact->vacuumFlags &= ~PROC_FREEZING_MULTI;
 
 		if (flags & FRM_INVALIDATE_XMAX)
 			freeze_xmax = true;
diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index ed7101f..0166978 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -77,6 +77,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"
@@ -864,8 +865,12 @@ GetNewMultiXactId(int nmembers, MultiXactOffset *offset)
 
 	debug_elog3(DEBUG2, "GetNew: for %d xids", nmembers);
 
-	/* MultiXactIdSetOldestMember() must have been called already */
-	Assert(MultiXactIdIsValid(OldestMemberMXactId[MyBackendId]));
+	/*
+	 * MultiXactIdSetOldestMember() must have been called already, but don't
+	 * check while freezing MultiXactIds.
+	 */
+	Assert((MyPgXact->vacuumFlags & PROC_FREEZING_MULTI) ||
+		   MultiXactIdIsValid(OldestMemberMXactId[MyBackendId]));
 
 	/* safety check, we should never get this far in a HS slave */
 	if (RecoveryInProgress())
diff --git a/src/include/storage/proc.h b/src/include/storage/proc.h
index 3b04d3c..7e53a3a 100644
--- a/src/include/storage/proc.h
+++ b/src/include/storage/proc.h
@@ -42,9 +42,10 @@ struct XidCache
 #define		PROC_IN_VACUUM		0x02	/* currently running lazy vacuum */
 #define		PROC_IN_ANALYZE		0x04	/* currently running analyze */
 #define		PROC_VACUUM_FOR_WRAPAROUND 0x08		/* set by autovac only */
+#define		PROC_FREEZING_MULTI	0x10	/* set while freezing multis */
 
 /* flags reset at EOXact */
-#define		PROC_VACUUM_STATE_MASK (0x0E)
+#define		PROC_VACUUM_STATE_MASK (0x1E)
 
 /*
  * We allow a small number of "weak" relation locks (AccesShareLock,
-- 
1.7.10.4

*** a/src/backend/access/transam/multixact.c
--- b/src/backend/access/transam/multixact.c
***************
*** 72,77 ****
--- 72,78 ----
  #include "catalog/pg_type.h"
  #include "commands/dbcommands.h"
  #include "funcapi.h"
+ #include "lib/ilist.h"
  #include "miscadmin.h"
  #include "pg_trace.h"
  #include "postmaster/autovacuum.h"
***************
*** 262,274 **** static MultiXactId *OldestVisibleMXactId;
   */
  typedef struct mXactCacheEnt
  {
- 	struct mXactCacheEnt *next;
  	MultiXactId multi;
  	int			nmembers;
  	MultiXactMember members[FLEXIBLE_ARRAY_MEMBER];
  } mXactCacheEnt;
  
! static mXactCacheEnt *MXactCache = NULL;
  static MemoryContext MXactContext = NULL;
  
  #ifdef MULTIXACT_DEBUG
--- 263,277 ----
   */
  typedef struct mXactCacheEnt
  {
  	MultiXactId multi;
  	int			nmembers;
+ 	dlist_node	node;
  	MultiXactMember members[FLEXIBLE_ARRAY_MEMBER];
  } mXactCacheEnt;
  
! #define MAX_CACHE_ENTRIES	256
! static dlist_head	MXactCache = DLIST_STATIC_INIT(MXactCache);
! static int			MXactCacheMembers = 0;
  static MemoryContext MXactContext = NULL;
  
  #ifdef MULTIXACT_DEBUG
***************
*** 1306,1312 **** mxactMemberComparator(const void *arg1, const void *arg2)
  static MultiXactId
  mXactCacheGetBySet(int nmembers, MultiXactMember *members)
  {
! 	mXactCacheEnt *entry;
  
  	debug_elog3(DEBUG2, "CacheGet: looking for %s",
  				mxid_to_string(InvalidMultiXactId, nmembers, members));
--- 1309,1315 ----
  static MultiXactId
  mXactCacheGetBySet(int nmembers, MultiXactMember *members)
  {
! 	dlist_iter	iter;
  
  	debug_elog3(DEBUG2, "CacheGet: looking for %s",
  				mxid_to_string(InvalidMultiXactId, nmembers, members));
***************
*** 1314,1321 **** mXactCacheGetBySet(int nmembers, MultiXactMember *members)
  	/* sort the array so comparison is easy */
  	qsort(members, nmembers, sizeof(MultiXactMember), mxactMemberComparator);
  
! 	for (entry = MXactCache; entry != NULL; entry = entry->next)
  	{
  		if (entry->nmembers != nmembers)
  			continue;
  
--- 1317,1326 ----
  	/* sort the array so comparison is easy */
  	qsort(members, nmembers, sizeof(MultiXactMember), mxactMemberComparator);
  
! 	dlist_foreach(iter, &MXactCache)
  	{
+ 		mXactCacheEnt *entry = dlist_container(mXactCacheEnt, node, iter.cur);
+ 
  		if (entry->nmembers != nmembers)
  			continue;
  
***************
*** 1326,1331 **** mXactCacheGetBySet(int nmembers, MultiXactMember *members)
--- 1331,1337 ----
  		if (memcmp(members, entry->members, nmembers * sizeof(MultiXactMember)) == 0)
  		{
  			debug_elog3(DEBUG2, "CacheGet: found %u", entry->multi);
+ 			dlist_move_head(&MXactCache, iter.cur);
  			return entry->multi;
  		}
  	}
***************
*** 1345,1356 **** mXactCacheGetBySet(int nmembers, MultiXactMember *members)
  static int
  mXactCacheGetById(MultiXactId multi, MultiXactMember **members)
  {
! 	mXactCacheEnt *entry;
  
  	debug_elog3(DEBUG2, "CacheGet: looking for %u", multi);
  
! 	for (entry = MXactCache; entry != NULL; entry = entry->next)
  	{
  		if (entry->multi == multi)
  		{
  			MultiXactMember *ptr;
--- 1351,1364 ----
  static int
  mXactCacheGetById(MultiXactId multi, MultiXactMember **members)
  {
! 	dlist_iter	iter;
  
  	debug_elog3(DEBUG2, "CacheGet: looking for %u", multi);
  
! 	dlist_foreach(iter, &MXactCache)
  	{
+ 		mXactCacheEnt *entry = dlist_container(mXactCacheEnt, node, iter.cur);
+ 
  		if (entry->multi == multi)
  		{
  			MultiXactMember *ptr;
***************
*** 1366,1371 **** mXactCacheGetById(MultiXactId multi, MultiXactMember **members)
--- 1374,1382 ----
  						mxid_to_string(multi,
  									   entry->nmembers,
  									   entry->members));
+ 
+ 			dlist_move_head(&MXactCache, iter.cur);
+ 
  			return entry->nmembers;
  		}
  	}
***************
*** 1409,1416 **** mXactCachePut(MultiXactId multi, int nmembers, MultiXactMember *members)
  	/* mXactCacheGetBySet assumes the entries are sorted, so sort them */
  	qsort(entry->members, nmembers, sizeof(MultiXactMember), mxactMemberComparator);
  
! 	entry->next = MXactCache;
! 	MXactCache = entry;
  }
  
  static char *
--- 1420,1435 ----
  	/* mXactCacheGetBySet assumes the entries are sorted, so sort them */
  	qsort(entry->members, nmembers, sizeof(MultiXactMember), mxactMemberComparator);
  
! 	dlist_push_head(&MXactCache, &entry->node);
! 	if (MXactCacheMembers++ >= MAX_CACHE_ENTRIES)
! 	{
! 		dlist_node *node;
! 
! 		node = dlist_tail_node(&MXactCache);
! 		dlist_delete(dlist_tail_node(&MXactCache));
! 		MXactCacheMembers--;
! 		pfree(dlist_container(mXactCacheEnt, node, node));
! 	}
  }
  
  static char *
***************
*** 1485,1491 **** AtEOXact_MultiXact(void)
  	 * a child of TopTransactionContext, we needn't delete it explicitly.
  	 */
  	MXactContext = NULL;
! 	MXactCache = NULL;
  }
  
  /*
--- 1504,1511 ----
  	 * a child of TopTransactionContext, we needn't delete it explicitly.
  	 */
  	MXactContext = NULL;
! 	dlist_init(&MXactCache);
! 	MXactCacheMembers = 0;
  }
  
  /*
***************
*** 1551,1557 **** PostPrepare_MultiXact(TransactionId xid)
  	 * Discard the local MultiXactId cache like in AtEOX_MultiXact
  	 */
  	MXactContext = NULL;
! 	MXactCache = NULL;
  }
  
  /*
--- 1571,1578 ----
  	 * Discard the local MultiXactId cache like in AtEOX_MultiXact
  	 */
  	MXactContext = NULL;
! 	dlist_init(&MXactCache);
! 	MXactCacheMembers = 0;
  }
  
  /*