Bug in ProcArrayApplyRecoveryInfo for snapshots crossing 4B, breaking replicas

From efb0e79d752102dd0fa066959cea517288cc6085 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Wed, 26 Jan 2022 19:24:21 +0100
Subject: [PATCH 1/2] Add TAP test

---
 src/test/recovery/t/028_wraparound_restart.pl | 172 ++++++++++++++++++
 1 file changed, 172 insertions(+)
 create mode 100644 src/test/recovery/t/028_wraparound_restart.pl

diff --git a/src/test/recovery/t/028_wraparound_restart.pl b/src/test/recovery/t/028_wraparound_restart.pl
new file mode 100644
index 00000000000..2be5537b6b3
--- /dev/null
+++ b/src/test/recovery/t/028_wraparound_restart.pl
@@ -0,0 +1,172 @@
+# Run the standard regression tests with streaming replication
+use strict;
+use warnings;
+use PostgreSQL::Test::Cluster;
+use PostgreSQL::Test::Utils;
+use Test::More tests => 36;
+use File::Basename;
+
+# Initialize primary node
+my $node_primary = PostgreSQL::Test::Cluster->new('primary');
+$node_primary->init(allows_streaming => 1);
+$node_primary->adjust_conf('postgresql.conf', 'max_connections', '25', 1);
+$node_primary->append_conf('postgresql.conf', 'max_prepared_transactions = 10');
+
+# needed so that vacuumdb freezes the template too, and we don't get warnings
+# about possible data loss due to wraparound
+$node_primary->start;
+$node_primary->psql(
+        'postgres',
+        qq[UPDATE pg_database SET datallowconn = 't']);
+$node_primary->stop;
+
+# reset WAL close to max XID (4294967295), in 4 smaller steps (~1B each)
+command_checks_all(
+	[ 'pg_resetwal', '-x', 1000000000, $node_primary->data_dir ],
+	0,
+	[qr''],
+	[qr''],
+	'reset WAL to 1B XID');
+
+command_checks_all(
+	[ 'dd', 'if=/dev/zero', 'of=' . $node_primary->data_dir . '/pg_xact/03B9', 'bs=1K', 'count=256'],
+	0,
+	[qr''],
+	[qr''],
+	'reset WAL to 1B XID');
+
+$node_primary->start;
+$node_primary->issues_sql_like(
+	[ 'vacuumdb', '--all', '--freeze', '--echo' ],
+	qr/statement: VACUUM.*statement: VACUUM/s,
+	'vacuum all databases');
+$node_primary->stop;
+
+command_checks_all(
+	[ 'pg_resetwal', '-x', 2000000000, $node_primary->data_dir ],
+	0,
+	[qr''],
+	[qr''],
+	'reset WAL to 2B XID');
+
+command_checks_all(
+	[ 'dd', 'if=/dev/zero', 'of=' . $node_primary->data_dir . '/pg_xact/0773', 'bs=1K', 'count=256'],
+	0,
+	[qr''],
+	[qr''],
+	'reset WAL to 2B XID');
+
+$node_primary->start;
+$node_primary->issues_sql_like(
+	[ 'vacuumdb', '--all', '--freeze', '--echo' ],
+	qr/statement: VACUUM.*statement: VACUUM/s,
+	'vacuum all databases');
+$node_primary->stop;
+
+command_checks_all(
+	[ 'pg_resetwal', '-x', 3000000000, $node_primary->data_dir ],
+	0,
+	[qr''],
+	[qr''],
+	'reset WAL to 3B XID');
+
+command_checks_all(
+	[ 'dd', 'if=/dev/zero', 'of=' . $node_primary->data_dir . '/pg_xact/0B2D', 'bs=1K', 'count=256'],
+	0,
+	[qr''],
+	[qr''],
+	'reset WAL to 3B XID');
+
+$node_primary->start;
+
+is( $node_primary->psql(
+        'postgres',
+        qq[SELECT datname
+    , age(datfrozenxid)
+    , current_setting('autovacuum_freeze_max_age') 
+FROM pg_database 
+ORDER BY 2 DESC]),
+    0,
+    'physical slot created on primary');
+
+$node_primary->issues_sql_like(
+	[ 'vacuumdb', '--all', '--freeze', '--echo' ],
+	qr/statement: VACUUM.*statement: VACUUM/s,
+	'vacuum all databases');
+$node_primary->stop;
+
+# the max is 4294967295, so this is within 100 transactions of wraparound
+command_checks_all(
+	[ 'pg_resetwal', '-x', 4294967200, $node_primary->data_dir ],
+	0,
+	[qr''],
+	[qr''],
+	'reset WAL to 4B XID');
+
+command_checks_all(
+	[ 'dd', 'if=/dev/zero', 'of=' . $node_primary->data_dir . '/pg_xact/0FFF', 'bs=1K', 'count=256'],
+	0,
+	[qr''],
+	[qr''],
+	'reset WAL to 4B XID');
+
+$node_primary->start;
+$node_primary->issues_sql_like(
+	[ 'vacuumdb', '--all', '--freeze', '--echo' ],
+	qr/statement: VACUUM.*statement: VACUUM/s,
+	'vacuum all databases');
+
+
+# now, start transactions with XID before/after the 4B limit
+my $main_in    = '';
+my $main_out   = '';
+my $main_timer = IPC::Run::timeout(180);
+
+my $main_h =
+  $node_primary->background_psql('postgres', \$main_in, \$main_out,
+	$main_timer, on_error_stop => 1);
+$main_in .= q(
+BEGIN;
+SELECT txid_current();
+\echo syncpoint1
+);
+pump $main_h until $main_out =~ /syncpoint1/ || $main_timer->is_expired;
+
+# run 200 trivial transactions to consume enough XIDs and cross 4B
+$node_primary->pgbench(
+	"-t 200 -n",
+	0,
+	[qr{}],
+	[qr{^$}],
+	'pgbench custom scripts',
+	{
+		'001_pgbench_custom_script_1@1' => q{-- select only
+SELECT txid_current();
+}
+	});
+
+$main_timer = IPC::Run::timeout(180);
+$main_h =
+  $node_primary->background_psql('postgres', \$main_in, \$main_out,
+	$main_timer, on_error_stop => 1);
+$main_in .= q(
+BEGIN;
+SELECT txid_current();
+\echo syncpoint1
+);
+pump $main_h until $main_out =~ /syncpoint1/ || $main_timer->is_expired;
+
+# Take backup and try starting a replica from the backup
+my $backup_name = 'my_backup';
+
+$node_primary->backup($backup_name);
+
+# Create streaming standby linking to primary
+my $node_standby_1 = PostgreSQL::Test::Cluster->new('standby_1');
+$node_standby_1->init_from_backup($node_primary, $backup_name,
+	has_streaming => 1);
+    
+$node_standby_1->start;
+
+$node_standby_1->stop;
+$node_primary->stop;
-- 
2.31.1

From 5570c1b4840999d6b6dd8bae699de6742b18fe73 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Sun, 23 Jan 2022 01:00:29 +0100
Subject: [PATCH 2/2] Fix ordering of XIDs in ProcArrayApplyRecoveryInfo

Commit 8431e296ea reworked ProcArrayApplyRecoveryInfo to sort XIDs
before adding them to KnownAssignedXids, but it used xidComparator for
that purpose, which simply compares the values as uint32 values. This
may easily confuse KnownAssignedXidsAdd() which enforces the logical
ordering by calling TransactionIdFollowsOrEquals() etc.

Hitting this issue is fairly easy - you just need two transactons, one
started before the 4B limit (e.g. XID 4294967290), the other sometime
after it (e.g. XID 1000). Logically (4294967290 <= 1000) but when
compared using xidComparator we try to add them in the opposite order.
Which makes KnownAssignedXidsAdd() fail with an error like this:

  ERROR: out-of-order XID insertion in KnownAssignedXids

This however only happens during replica initialization - so you have to
restart (or create) a replica while there are such transactions with
contradictory XID ordering. Long-running transactions naturally increase
the likelihood of hitting this issue. Once the replica gets into this
state, it can't be started (even if the old transactions are terminated
in some way).

Fixed by sorting the XIDs logically - this is fine because we're dealing
with normal XIDs (because it's XIDs assigned to backends) and from the
same wraparound epoch (otherwise the backends could not be running at
the same time on the primary node). So there are no problems with the
triangle inequality, which is why xidComparator compares raw values.

Patch by me. Investigation and root cause analysis by Abhijit Menon-Sen.

This issue is present in all releases since 9.4, however releases up to
9.6 are EOL already so backpatch to 10 only.

Reviewed-by: Abhijit Menon-Sen
Reviewed-by: Alvaro Herrera
Backpatch-through: 10
---
 src/backend/storage/ipc/procarray.c |  7 ++++++-
 src/backend/utils/adt/xid.c         | 26 ++++++++++++++++++++++++++
 src/include/utils/builtins.h        |  1 +
 3 files changed, 33 insertions(+), 1 deletion(-)

diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index 3be60402890..9d3efb7d80e 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -1164,8 +1164,13 @@ ProcArrayApplyRecoveryInfo(RunningTransactions running)
 		/*
 		 * Sort the array so that we can add them safely into
 		 * KnownAssignedXids.
+		 *
+		 * We have to sort them logically, because in KnownAssignedXidsAdd we
+		 * call TransactionIdFollowsOrEquals and so on. But we know these XIDs
+		 * come from RUNNING_XACTS, which means there are only normal XIDs from
+		 * the same epoch, so this is safe.
 		 */
-		qsort(xids, nxids, sizeof(TransactionId), xidComparator);
+		qsort(xids, nxids, sizeof(TransactionId), xidLogicalComparator);
 
 		/*
 		 * Add the sorted snapshot into KnownAssignedXids.  The running-xacts
diff --git a/src/backend/utils/adt/xid.c b/src/backend/utils/adt/xid.c
index e6633e9cffe..9b4ceaea47f 100644
--- a/src/backend/utils/adt/xid.c
+++ b/src/backend/utils/adt/xid.c
@@ -145,6 +145,32 @@ xidComparator(const void *arg1, const void *arg2)
 	return 0;
 }
 
+/*
+ * xidLogicalComparator
+ *		qsort comparison function for XIDs
+ *
+ * This is used to compare only XIDs from the same epoch (e.g. for backends
+ * running at the same time). So there must be only normal XIDs, so there's
+ * no issue with triangle inequality.
+ */
+int
+xidLogicalComparator(const void *arg1, const void *arg2)
+{
+	TransactionId xid1 = *(const TransactionId *) arg1;
+	TransactionId xid2 = *(const TransactionId *) arg2;
+
+	Assert(TransactionIdIsNormal(xid1));
+	Assert(TransactionIdIsNormal(xid2));
+
+	if (TransactionIdPrecedes(xid1, xid2))
+		return -1;
+
+	if (TransactionIdPrecedes(xid2, xid1))
+		return 1;
+
+	return 0;
+}
+
 Datum
 xid8toxid(PG_FUNCTION_ARGS)
 {
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 7ac4780e3fc..d8f05a7df3a 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -87,6 +87,7 @@ extern void text_to_cstring_buffer(const text *src, char *dst, size_t dst_len);
 
 /* xid.c */
 extern int	xidComparator(const void *arg1, const void *arg2);
+extern int	xidLogicalComparator(const void *arg1, const void *arg2);
 
 /* inet_cidr_ntop.c */
 extern char *pg_inet_cidr_ntop(int af, const void *src, int bits,
-- 
2.31.1