v3-0001-Avoid-update-conflict-out-serialization-anomalies.patch

From e9b13892441c257b0609e3855f349e7b7ba65b0c Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Sun, 7 Jun 2020 19:15:48 -0700
Subject: [PATCH v3] Avoid update conflict out serialization anomalies.

SSI's HeapCheckForSerializableConflictOut() test failed to correctly
handle conditions involving a concurrent update in all cases.  A
HeapCheckForSerializableConflictOut() caller (typically from a SELECT
statement) could end up using the same updater's XID for both the
original tuple, and the successor tuple, missing the XID of the xact
that created the original tuple entirely.  This only happened when
neither tuple from the chain was visible to the
HeapCheckForSerializableConflictOut() caller.

The observable symptoms of this bug were subtle.  A pair of transactions
could commit, with the later transaction failing to observe the effects
of the earlier transaction (because of the confusion created by the
update to the non-visible row).  This bug went unnoticed for so long.
It dates all the way back to commit dafaa3ef, which added SSI.

To fix, make sure that we check both the original tuple's xmin (i.e.
the XID of the transaction that create the tuple), as well as the
updater's XID.

Author: Peter Geoghegan
Reported-By: Kyle Kingsbury
Reviewed-By: Thomas Munro
Discussion: https://postgr.es/m/db7b729d-0226-d162-a126-8a8ab2dc4443@jepsen.io
Backpatch: All supported versions
---
 src/backend/access/heap/heapam.c              | 22 ++++++---
 .../expected/update-conflict-out.out          | 17 +++++++
 src/test/isolation/isolation_schedule         |  1 +
 .../isolation/specs/update-conflict-out.spec  | 45 +++++++++++++++++++
 4 files changed, 80 insertions(+), 5 deletions(-)
 create mode 100644 src/test/isolation/expected/update-conflict-out.out
 create mode 100644 src/test/isolation/specs/update-conflict-out.spec

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 94eb37d48d..7023e78065 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -9007,6 +9007,11 @@ HeapCheckForSerializableConflictOut(bool visible, Relation relation,
 	 * while it is visible to us.  The "visible" bool indicates whether the
 	 * tuple is visible to us, while HeapTupleSatisfiesVacuum checks what else
 	 * is going on with it.
+	 *
+	 * In the event of an updated tuple that is not visible to us, the xmin of
+	 * the tuple will be used -- not the updater's xid.  The successor tuple
+	 * is often handled by another call here, at which point we'll check the
+	 * updater's xid.
 	 */
 	htsvResult = HeapTupleSatisfiesVacuum(tuple, TransactionXmin, buffer);
 	switch (htsvResult)
@@ -9017,17 +9022,24 @@ HeapCheckForSerializableConflictOut(bool visible, Relation relation,
 			xid = HeapTupleHeaderGetXmin(tuple->t_data);
 			break;
 		case HEAPTUPLE_RECENTLY_DEAD:
-			if (!visible)
-				return;
-			xid = HeapTupleHeaderGetUpdateXid(tuple->t_data);
-			break;
 		case HEAPTUPLE_DELETE_IN_PROGRESS:
-			xid = HeapTupleHeaderGetUpdateXid(tuple->t_data);
+			if (visible)
+				xid = HeapTupleHeaderGetUpdateXid(tuple->t_data);
+			else
+				xid = HeapTupleHeaderGetXmin(tuple->t_data);
+
+			if (TransactionIdPrecedes(xid, TransactionXmin))
+			{
+				/* This is like the HEAPTUPLE_DEAD case */
+				Assert(!visible);
+				return;
+			}
 			break;
 		case HEAPTUPLE_INSERT_IN_PROGRESS:
 			xid = HeapTupleHeaderGetXmin(tuple->t_data);
 			break;
 		case HEAPTUPLE_DEAD:
+			Assert(!visible);
 			return;
 		default:
 
diff --git a/src/test/isolation/expected/update-conflict-out.out b/src/test/isolation/expected/update-conflict-out.out
new file mode 100644
index 0000000000..8624bb43cb
--- /dev/null
+++ b/src/test/isolation/expected/update-conflict-out.out
@@ -0,0 +1,17 @@
+Parsed test spec with 3 sessions
+
+starting permutation: foo_first bar_first bar_insert foo_insert foo_commit trouble_update bar_select bar_commit trouble_abort
+step foo_first: SELECT * FROM txn1;
+id             val            
+
+step bar_first: SELECT * FROM txn1;
+id             val            
+
+step bar_insert: INSERT INTO txn1 SELECT -42, 'bar_insert';
+step foo_insert: INSERT INTO txn0 SELECT 7, 'foo-insert';
+step foo_commit: COMMIT;
+step trouble_update: UPDATE txn0 SET val = 'add physical version for "bar_select"' WHERE id = 7;
+step bar_select: SELECT * FROM txn0 WHERE id = 7;
+ERROR:  could not serialize access due to read/write dependencies among transactions
+step bar_commit: COMMIT;
+step trouble_abort: ABORT;
diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule
index 2873cd7c21..218c87b24b 100644
--- a/src/test/isolation/isolation_schedule
+++ b/src/test/isolation/isolation_schedule
@@ -18,6 +18,7 @@ test: two-ids
 test: multiple-row-versions
 test: index-only-scan
 test: predicate-lock-hot-tuple
+test: update-conflict-out
 test: deadlock-simple
 test: deadlock-hard
 test: deadlock-soft
diff --git a/src/test/isolation/specs/update-conflict-out.spec b/src/test/isolation/specs/update-conflict-out.spec
new file mode 100644
index 0000000000..83bef30644
--- /dev/null
+++ b/src/test/isolation/specs/update-conflict-out.spec
@@ -0,0 +1,45 @@
+# Test for interactions between SSI's "conflict out" handling for heapam and
+# concurrently updated tuple
+#
+# See bug report:
+# https://postgr.es/m/db7b729d-0226-d162-a126-8a8ab2dc4443%40jepsen.io
+
+setup
+{
+  CREATE TABLE txn0(id int4 PRIMARY KEY, val TEXT);
+  CREATE TABLE txn1(id int4 PRIMARY KEY, val TEXT);
+}
+
+teardown
+{
+  DROP TABLE txn0;
+  DROP TABLE txn1;
+}
+
+session "foo"
+setup                  { BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE; }
+step "foo_first"       { SELECT * FROM txn1; }
+step "foo_insert"      { INSERT INTO txn0 SELECT 7, 'foo-insert'; }
+step "foo_commit"      { COMMIT; }
+
+session "bar"
+setup                  { BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE; }
+step "bar_first"       { SELECT * FROM txn1; }
+step "bar_insert"      { INSERT INTO txn1 SELECT -42, 'bar_insert'; }
+step "bar_select"      { SELECT * FROM txn0 WHERE id = 7; }
+step "bar_commit"      { COMMIT; }
+
+# This session creates the conditions that confused bar's "conflict out"
+# handling:
+session "trouble"
+setup                  { BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE; }
+step "trouble_update"  { UPDATE txn0 SET val = 'add physical version for "bar_select"' WHERE id = 7; }
+step "trouble_abort"   { ABORT; }
+
+permutation "foo_first" "bar_first"
+    "bar_insert"
+    "foo_insert" "foo_commit"
+    "trouble_update"   # Updates tuple...
+    "bar_select"       # Should observe one distinct XID per version
+    "bar_commit"       # "bar" should fail here at the latest
+    "trouble_abort"
-- 
2.25.1