Subject: [PATCH 1460/1461] Rework techniques for getting to top level transaction when using an XID from MVCC data, based on concerns form Heikki and Tom. Use SubTransGetTopmostTransaction, checking both before and after for a TranactionId before TransactionXmin, which would indicate a transaction too early to overlap, and therefore not able to generate a conflict with the current transaction.

From: Kevin Grittner <[email-masked]>
Date: Sat, 18 Sep 2010 11:08:40 -0500

---
 src/backend/access/transam/varsup.c      |    4 +
 src/backend/storage/lmgr/predicate.c     |  146 ++++++++++++------------------
 src/include/storage/predicate.h          |    1 +
 src/include/storage/predicate_internal.h |   15 ++--
 4 files changed, 70 insertions(+), 96 deletions(-)

diff --git a/src/backend/access/transam/varsup.c b/src/backend/access/transam/varsup.c
index efe11a9..8811e24 100644
--- a/src/backend/access/transam/varsup.c
+++ b/src/backend/access/transam/varsup.c
@@ -20,6 +20,7 @@
 #include "miscadmin.h"
 #include "postmaster/autovacuum.h"
 #include "storage/pmsignal.h"
+#include "storage/predicate.h"
 #include "storage/proc.h"
 #include "utils/builtins.h"
 #include "utils/syscache.h"
@@ -156,9 +157,12 @@ GetNewTransactionId(bool isSubXact)
 	 * holds 32K or more transactions, so we don't have to do this very often.
 	 *
 	 * Extend pg_subtrans too.
+	 * If it's top level, the predicate locking system also needs to know.
 	 */
 	ExtendCLOG(xid);
 	ExtendSUBTRANS(xid);
+	if (!isSubXact)
+		RegisterPredicateLockingXid(xid);
 
 	/*
 	 * Now advance the nextXid counter.  This must not happen until after we
diff --git a/src/backend/storage/lmgr/predicate.c b/src/backend/storage/lmgr/predicate.c
index 76e1277..974b95c 100644
--- a/src/backend/storage/lmgr/predicate.c
+++ b/src/backend/storage/lmgr/predicate.c
@@ -116,6 +116,7 @@
  *
  * predicate lock maintenance
  *		RegisterSerializableTransaction(Snapshot snapshot)
+ *		RegisterPredicateLockingXid(void)
  *		PredicateLockRelation(Relation relation)
  *		PredicateLockPage(Relation relation, BlockNumber blkno)
  *		PredicateLockTuple(Relation relation, HeapTuple tuple)
@@ -137,6 +138,7 @@
 
 #include "postgres.h"
 
+#include "access/subtrans.h"
 #include "access/transam.h"
 #include "access/twophase.h"
 #include "access/xact.h"
@@ -293,7 +295,6 @@ static bool GetParentPredicateLockTag(const PREDICATELOCKTARGETTAG *tag,
 						  PREDICATELOCKTARGETTAG *parent);
 static void DecrementParentLocks(const PREDICATELOCKTARGETTAG *targettag);
 static void PredicateLockAcquire(const PREDICATELOCKTARGETTAG *tag);
-static void EnsureMySerializableXidExists(void);
 static void ClearOldPredicateLocks(void);
 static bool XidIsConcurrent(TransactionId xid);
 static void FlagRWConflict(SERIALIZABLEXACT *reader, SERIALIZABLEXACT *writer);
@@ -612,7 +613,6 @@ RegisterSerializableTransaction(const Snapshot snapshot)
 	sxact->finishedBefore = InvalidTransactionId;
 	sxact->xmin = snapshot->xmin;
 	SHMQueueInit(&(sxact->predicateLocks));
-	SHMQueueInit(&(sxact->xids));
 	SHMQueueElemInit(&(sxact->finishedLink));
 	sxact->rolledBack = false;
 	LWLockRelease(SerializableXactHashLock);
@@ -632,55 +632,50 @@ RegisterSerializableTransaction(const Snapshot snapshot)
 }
 
 /*
- * Make sure we have a SERIALIZABLEXACT reference in MySerializableXact.
- * It should be current for this process and be contained in
- * SerializableXidHash.
+ * Register the top level XID in SerializableXidHash.
+ * Also store it for easy reference in MySerializableXact.
  */
-static void
-EnsureMySerializableXidExists(void)
+void
+RegisterPredicateLockingXid(const TransactionId xid)
 {
-	TransactionId xid;
-
-	Assert(MySerializableXact != InvalidSerializableXact);
-
-	MySerializableXact->topXid = GetTopTransactionIdIfAny();
+	SERIALIZABLEXIDTAG sxidtag;
+	SERIALIZABLEXID *sxid;
+	bool		found;
 
 	/*
-	 * If this isn't the xid we've most recently seen for this vxid, make sure
-	 * it's in the hash table.
+	 * If we're not tracking predicate lock data for this transaction,
+	 * we should ignore the request and return quickly.
 	 */
-	xid = GetCurrentTransactionIdIfAny();
-	if (MyXid != xid)
-	{
-		SERIALIZABLEXIDTAG sxidtag;
-		SERIALIZABLEXID *sxid;
-		bool		found;
+	if (MySerializableXact == InvalidSerializableXact)
+		return;
 
-		Assert(TransactionIdIsValid(xid));
+	/* This should only be done once per transaction. */
+	Assert(MySerializableXact->topXid == InvalidTransactionId);
 
-		sxidtag.xid = xid;
-		LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
-		sxid = (SERIALIZABLEXID *) hash_search(SerializableXidHash,
-											   &sxidtag,
-											   HASH_ENTER, &found);
-		if (!sxid)
-			ereport(ERROR,
-					(errcode(ERRCODE_OUT_OF_MEMORY),
-					 errmsg("out of shared memory"),
-					 errhint("You might need to increase max_predicate_locks_per_transaction.")));
+	/* We should have a valid XID and be at the top level. */
+	Assert(TransactionIdIsValid(xid));
 
-		/* Initialize the structure. */
-		if (!found)
-		{
-			sxid->myXact = (SERIALIZABLEXACT *) MySerializableXact;
-			SHMQueueInsertBefore(&(((SERIALIZABLEXACT *) MySerializableXact)->xids),
-								 &(sxid->xactLink));
-		}
-		LWLockRelease(SerializableXactHashLock);
-		MyXid = xid;
-	}
+	MySerializableXact->topXid = xid;
+
+	sxidtag.xid = xid;
+	LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
+	sxid = (SERIALIZABLEXID *) hash_search(SerializableXidHash,
+										   &sxidtag,
+										   HASH_ENTER, &found);
+	if (!sxid)
+		ereport(ERROR,
+				(errcode(ERRCODE_OUT_OF_MEMORY),
+				  errmsg("out of shared memory"),
+				  errhint("You might need to increase max_predicate_locks_per_transaction.")));
+
+	Assert(!found);
+
+	/* Initialize the structure. */
+	sxid->myXact = (SERIALIZABLEXACT *) MySerializableXact;
+	LWLockRelease(SerializableXactHashLock);
 }
 
+
 /*
  * Check whether there are any predicate locks held by any transaction
  * for the page at the given block number.
@@ -1053,8 +1048,6 @@ PredicateLockAcquire(const PREDICATELOCKTARGETTAG *targettag)
 	PREDICATELOCK *lock;
 	LOCALPREDICATELOCK *locallock;
 
-	EnsureMySerializableXidExists();
-
 	/* Do we have the lock already, or a covering lock? */
 	if (PredicateLockExists(targettag))
 		return;
@@ -1201,28 +1194,22 @@ PredicateLockTuple(const Relation relation, const HeapTuple tuple)
 		return;
 
 	/*
-	 * If it's a heap tuple, return if this xact wrote it.  It might be useful
-	 * to pass in the xmin from the tuple as another parameter.
+	 * If it's a heap tuple, return if this xact wrote it.
 	 */
 	if (relation->rd_index == NULL)
 	{
-		SERIALIZABLEXIDTAG sxidtag;
-		SERIALIZABLEXID *sxid;
-
-		sxidtag.xid = HeapTupleHeaderGetXmin(tuple->t_data);
-		LWLockAcquire(SerializableXactHashLock, LW_SHARED);
-		sxid = (SERIALIZABLEXID *)
-			hash_search(SerializableXidHash, &sxidtag, HASH_FIND, NULL);
-		if (sxid)
+		TransactionId xid;
+
+		xid = HeapTupleHeaderGetXmin(tuple->t_data);
+		if (TransactionIdFollowsOrEquals(xid, TransactionXmin))
 		{
-			if (sxid->myXact == MySerializableXact)
+			xid = SubTransGetTopmostTransaction(xid);
+			if (xid == GetTopTransactionIdIfAny())
 			{
 				/* We wrote it; we already have a write lock. */
-				LWLockRelease(SerializableXactHashLock);
 				return;
 			}
 		}
-		LWLockRelease(SerializableXactHashLock);
 	}
 
 	tid = &(tuple->t_self);
@@ -1731,7 +1718,7 @@ static void
 ReleaseOneSerializableXact(SERIALIZABLEXACT *sxact)
 {
 	PREDICATELOCK *predlock;
-	SERIALIZABLEXID *sxid;
+	SERIALIZABLEXIDTAG sxidtag;
 
 	Assert(sxact != NULL);
 	Assert(sxact->rolledBack || SxactIsCommitted(sxact));
@@ -1783,31 +1770,13 @@ ReleaseOneSerializableXact(SERIALIZABLEXACT *sxact)
 	}
 	LWLockRelease(SerializablePredicateLockListLock);
 
-	/* Get rid of the xids and the record of the transaction itself. */
-	LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
-	sxid = (SERIALIZABLEXID *)
-		SHMQueueNext(&(sxact->xids),
-					 &(sxact->xids),
-					 offsetof(SERIALIZABLEXID, xactLink));
-	while (sxid)
-	{
-		SERIALIZABLEXID *nextsxid;
-		SERIALIZABLEXIDTAG tag;
-
-		nextsxid = (SERIALIZABLEXID *)
-			SHMQueueNext(&(sxact->xids),
-						 &(sxid->xactLink),
-						 offsetof(SERIALIZABLEXID, xactLink));
-		tag = sxid->tag;
-		hash_search(SerializableXidHash, &tag, HASH_REMOVE, NULL);
-
-		/*
-		 * No need to do retail removal from transaction object; it's going
-		 * away.
-		 */
-		sxid = nextsxid;
-	}
 	SHMQueueDelete(&(sxact->finishedLink));
+
+	/* Get rid of the xid and the record of the transaction itself. */
+	sxidtag.xid = sxact->topXid;
+	LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
+	if (sxidtag.xid != InvalidTransactionId)
+		hash_search(SerializableXidHash, &sxidtag, HASH_REMOVE, NULL);
 	hash_search(SerializableXactHash, &(sxact->tag), HASH_REMOVE, NULL);
 	LWLockRelease(SerializableXactHashLock);
 }
@@ -1903,6 +1872,13 @@ CheckForSerializableConflictOut(const bool valid, const Relation relation,
 		xid = HeapTupleHeaderGetXmin(tuple->t_data);
 	}
 
+	/* Bail out if xid is too early to be a conflict. */
+	if (TransactionIdPrecedes(xid, TransactionXmin))
+		return;
+	xid = SubTransGetTopmostTransaction(xid);
+	if (TransactionIdPrecedes(xid, TransactionXmin))
+		return;
+
 	/*
 	 * It's OK to look for conflicts with a share lock, and record them with
 	 * an exclusive lock when found; we just have to release the shared lock
@@ -1949,12 +1925,6 @@ CheckForSerializableConflictOut(const bool valid, const Relation relation,
 	sxacttag = sxact->tag;
 	LWLockRelease(SerializableXactHashLock);
 
-	/*
-	 * Make sure we have somewhere to record a conflict against this
-	 * transaction.
-	 */
-	EnsureMySerializableXidExists();
-
 	LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
 	sxact = (SERIALIZABLEXACT *)
 		hash_search(SerializableXactHash, &sxacttag, HASH_FIND, NULL);
@@ -2184,8 +2154,6 @@ CheckForSerializableConflictIn(const Relation relation, const HeapTuple tuple,
 	if (SkipSerialization(relation))
 		return;
 
-	EnsureMySerializableXidExists();
-
 	/*
 	 * It is important that we check for locks from the finest granularity to
 	 * the coarsest granularity, so that granularity promotion doesn't cause
diff --git a/src/include/storage/predicate.h b/src/include/storage/predicate.h
index 7dcc2af..2cc20ab 100644
--- a/src/include/storage/predicate.h
+++ b/src/include/storage/predicate.h
@@ -37,6 +37,7 @@ extern bool PageIsPredicateLocked(const Relation relation, const BlockNumber blk
 
 /* predicate lock maintenance */
 extern void RegisterSerializableTransaction(const Snapshot snapshot);
+extern void RegisterPredicateLockingXid(const TransactionId xid);
 extern void PredicateLockRelation(const Relation relation);
 extern void PredicateLockPage(const Relation relation, const BlockNumber blkno);
 extern void PredicateLockTuple(const Relation relation, const HeapTuple tuple);
diff --git a/src/include/storage/predicate_internal.h b/src/include/storage/predicate_internal.h
index 7cdb5af..d6a2b8c 100644
--- a/src/include/storage/predicate_internal.h
+++ b/src/include/storage/predicate_internal.h
@@ -74,7 +74,6 @@ typedef struct SERIALIZABLEXACT
 										 * serializable xids are before this. */
 	TransactionId xmin;			/* the transaction's snapshot xmin */
 	SHM_QUEUE	predicateLocks; /* list of associated PREDICATELOCK objects */
-	SHM_QUEUE	xids;			/* list of associated SERIALIZABLEXID objects */
 	SHM_QUEUE	finishedLink;	/* list link in
 								 * FinishedSerializableTransactions */
 	bool		rolledBack;		/* ignore conflicts when true; allows deferred
@@ -93,8 +92,8 @@ typedef struct SERIALIZABLEXIDTAG
 
 /*
  * The SERIALIZABLEXID struct provides a link from a TransactionId for a
- * serializable transaction or subtransaction to the related SERIALIZABLEXACT
- * record.
+ * serializable transaction to the related SERIALIZABLEXACT record, even if
+ * the transaction has completed and its connection has been closed.
  * 
  * A hash table of these objects is maintained in shared memory to provide a
  * quick way to find the top level transaction information for a serializable
@@ -104,8 +103,12 @@ typedef struct SERIALIZABLEXIDTAG
  * allows a fast link from MVCC transaction IDs to the related serializable
  * transaction hash table entry.
  *
- * These are created as the transaction and its subtransactions write data,
- * and are kept until the cleanup of the top level transaction.
+ * These are created as new top level transaction IDs are first assigned to
+ * transactions which are participating in predicate locking.  They are
+ * removed with their related serializable transaction objects.
+ *
+ * The SubTransGetTopmostTransaction method is used where necessary to get
+ * from an XID which might be from a subtransaction to the top level XID.
  */
 typedef struct SERIALIZABLEXID
 {
@@ -114,8 +117,6 @@ typedef struct SERIALIZABLEXID
 
 	/* data */
 	SERIALIZABLEXACT *myXact;	/* pointer to the top level transaction data */
-	SHM_QUEUE	xactLink;		/* list link in SERIALIZABLEXACT's list of
-								 * xids */
 } SERIALIZABLEXID;

-- 
1.6.3.3