Subject: [PATCH 1461/1461] Replace the hash table for SERIALIZABLEXACT objects with a list. The hash table was really only being used for memory allocation purposes; it was the SHM_QUEUE objects forming lists which really mattered. That seemed inefficient and overly hacky, so a simple shared memory list implementation using SHM_QUEUE was created. The use of SHM_QUEUE is hidden, and all access is through four small functions, but no effort was made to really turn the list into a proper "black box" or generalize it.

From: Kevin Grittner <[email-masked]>
Date: Tue, 21 Sep 2010 10:11:26 -0500

---
 src/backend/storage/lmgr/predicate.c     |  186 +++++++++++++++++++++++-------
 src/include/storage/predicate_internal.h |   32 +++++
 2 files changed, 177 insertions(+), 41 deletions(-)

diff --git a/src/backend/storage/lmgr/predicate.c b/src/backend/storage/lmgr/predicate.c
index 974b95c..44c86e0 100644
--- a/src/backend/storage/lmgr/predicate.c
+++ b/src/backend/storage/lmgr/predicate.c
@@ -257,10 +257,21 @@ TransactionId SerializableGlobalXmin = InvalidTransactionId;
 int			SerializableGlobalXminCount = 0;
 
 /*
+ * This provides a list of objects in order to track transactions
+ * participating in predicate locking.  Entries in the list are fixed size,
+ * and reside in shared memory.  The memory address of an entry must remain
+ * fixed during its lifetime.  The list will be protected from concurrent
+ * update externally; no provision is made in this code to manage that.  The
+ * number of entries in the list, and the size allowed for each entry is
+ * fixed upon creation.
+ */
+static PredTranList PredLockTranList;
+
+
+/*
  * The predicate locking hash tables are in shared memory.
  * Each backend keeps pointers to them.
  */
-static HTAB *SerializableXactHash;
 static HTAB *SerializableXidHash;
 static HTAB *PredicateLockTargetHash;
 static HTAB *PredicateLockHash;
@@ -275,16 +286,19 @@ static HTAB *LocalPredicateLockHash = NULL;
 /*
  * Keep a pointer to the currently-running serializable transaction (if any)
  * for quick reference.
+ * TODO SSI: Remove volatile qualifier and the then-unnecessary casts?
  */
 static volatile SERIALIZABLEXACT *MySerializableXact = InvalidSerializableXact;
 
-/* TODO SSI: Remove volatile qualifier and the then-unnecessary casts? */
-
-/* The most recently used xid within this transaction, for optimizations. */
-static TransactionId MyXid = InvalidTransactionId;

 /* local functions */
+
+static SERIALIZABLEXACT *CreatePredTran(void);
+static void ReleasePredTran(SERIALIZABLEXACT *sxact);
+static SERIALIZABLEXACT *FirstPredTran(void);
+static SERIALIZABLEXACT *NextPredTran(SERIALIZABLEXACT *sxact);
+
 static uint32 predicatelock_hash(const void *key, Size keysize);
 static void ReleaseOneSerializableXact(SERIALIZABLEXACT *sxact);
 static bool PredicateLockExists(const PREDICATELOCKTARGETTAG *newtargettag);
@@ -302,6 +316,78 @@ static void CheckTargetForConflictsIn(PREDICATELOCKTARGETTAG *targettag);
 static void OnConflict_CheckForSerializationFailure(const SERIALIZABLEXACT *reader,
 										const SERIALIZABLEXACT *writer);
 
+
+/*
+ * These functions are a simple implementation of a list for this specific
+ * type of struct.  If there is ever a generalized shared memory list, we
+ * should probably switch to that.
+ */
+static SERIALIZABLEXACT *
+CreatePredTran(void)
+{
+	PredTranListElement ptle;
+
+	ptle = (PredTranListElement)
+		SHMQueueNext(&PredLockTranList->availableList,
+					 &PredLockTranList->availableList,
+					 offsetof(PredTranListElementData, link));
+	SHMQueueDelete(&ptle->link);
+	SHMQueueInsertBefore(&PredLockTranList->activeList, &ptle->link);
+	return &ptle->sxact;
+}
+
+static void
+ReleasePredTran(SERIALIZABLEXACT *sxact)
+{
+	PredTranListElement ptle;
+
+	Assert(ShmemAddrIsValid(sxact));
+
+	ptle = (PredTranListElement)
+		(((char *) sxact)
+			- offsetof(PredTranListElementData, sxact)
+			+ offsetof(PredTranListElementData, link));
+	SHMQueueDelete(&ptle->link);
+	SHMQueueInsertBefore(&PredLockTranList->availableList, &ptle->link);
+}
+
+static SERIALIZABLEXACT *
+FirstPredTran(void)
+{
+	PredTranListElement ptle;
+
+	ptle = (PredTranListElement)
+			SHMQueueNext(&PredLockTranList->activeList,
+						 &PredLockTranList->activeList,
+						 offsetof(PredTranListElementData, link));
+	if (!ptle)
+		return NULL;
+
+	return &ptle->sxact;
+}
+
+static SERIALIZABLEXACT *
+NextPredTran(SERIALIZABLEXACT *sxact)
+{
+	PredTranListElement ptle;
+
+	Assert(ShmemAddrIsValid(sxact));
+
+	ptle = (PredTranListElement)
+		(((char *) sxact)
+			- offsetof(PredTranListElementData, sxact)
+			+ offsetof(PredTranListElementData, link));
+	ptle = (PredTranListElement)
+			SHMQueueNext(&PredLockTranList->activeList,
+						 &ptle->link,
+						 offsetof(PredTranListElementData, link));
+	if (!ptle)
+		return NULL;
+
+	return &ptle->sxact;
+}
+
+
 /*
  * InitPredicateLocks -- Initialize the predicate locking data structures.
  *
@@ -319,6 +405,7 @@ InitPredicateLocks(void)
 	int			hash_flags;
 	long		init_table_size,
 				max_table_size;
+	Size		requestSize;
 	bool		found;
 
 	/*
@@ -375,25 +462,46 @@ InitPredicateLocks(void)
 	init_table_size = max_table_size / 2;
 
 	/*
-	 * Allocate hash table for SERIALIZABLEXACT structs.  This stores per-vxid
-	 * information for serializable transactions which have accessed data.
+	 * Allocate a list to hold information on transaction participating in
+	 * predicate locking.
+	 *
+	 * Assume an average of 10 predicate locking transactions per backend.
+	 * That may seem high, but each transaction must be kept until every
+	 * overlapping predicate locking transaction has completed, so we have
+	 * to tolerate the occassional long-running transaction.
 	 */
-	MemSet(&info, 0, sizeof(info));
-	info.keysize = sizeof(SERIALIZABLEXACTTAG);
-	info.entrysize = sizeof(SERIALIZABLEXACT);
-	info.hash = tag_hash;
-	hash_flags = (HASH_ELEM | HASH_FUNCTION);
-
-	SerializableXactHash = ShmemInitHash("SERIALIZABLEXACT hash",
-										 init_table_size,
-										 max_table_size,
-										 &info,
-										 hash_flags);
-
-	/* Assume an average of 10 serializable xids per backend. */
 	max_table_size *= 10;
 	init_table_size *= 10;
 
+	PredLockTranList = ShmemInitStruct("PredTranList",
+									   PredTranListDataSize,
+									   &found);
+	if (!found)
+	{
+		int i;
+
+		SHMQueueInit(&PredLockTranList->availableList);  // available elements
+		SHMQueueInit(&PredLockTranList->activeList);  // active elements
+		requestSize = mul_size((Size) max_table_size,
+							   PredTranListElementDataSize);
+		PredLockTranList->element = ShmemAlloc(requestSize);
+		if (PredLockTranList->element == NULL)
+			ereport(ERROR,
+					(errcode(ERRCODE_OUT_OF_MEMORY),
+					  errmsg("not enough shared memory for elements of data structure"
+							" \"%s\" (%lu bytes requested)",
+							"PredTranList", (unsigned long) requestSize)));
+		PredLockTranList->entryLimit = max_table_size;  // get from GUC?
+		PredLockTranList->entryCount = 0;  // starts empty
+		/* Add all elements to available list, clean. */
+		memset(PredLockTranList->element, 0, requestSize);
+		for (i = 0; i < max_table_size; i++)
+		{
+			SHMQueueInsertBefore(&(PredLockTranList->availableList),
+								 &(PredLockTranList->element[i].link));
+		}
+	}
+
 	/*
 	 * Allocate hash table for SERIALIZABLEXID structs.  This stores per-xid
 	 * information for serializable transactions which have accessed data.
@@ -447,13 +555,14 @@ PredicateLockShmemSize(void)
 	 */
 	size = add_size(size, size / 10);
 
-	/* serializable transaction table */
+	/* transaction list */
 	max_table_size = MaxBackends;
-	size = add_size(size, hash_estimate_size(max_table_size,
-											 sizeof(SERIALIZABLEXACT)));
-
-	/* serializable subtransaction table */
 	max_table_size *= 10;
+	size = add_size(size, PredTranListDataSize);
+	size = add_size(size, mul_size((Size) max_table_size,
+								   PredTranListElementDataSize));
+
+	/* transaction xid table */
 	size = add_size(size, hash_estimate_size(max_table_size,
 											 sizeof(SERIALIZABLEXID)));
 
@@ -561,7 +670,7 @@ GetPredicateLockStatusData(void)
 /*
  * Make sure we have a SERIALIZABLEXACT reference in MySerializableXact.
  * It should be current for this process and be contained in
- * SerializableXactHash.
+ * PredLockTranList.
  */
 void
 RegisterSerializableTransaction(const Snapshot snapshot)
@@ -569,7 +678,6 @@ RegisterSerializableTransaction(const Snapshot snapshot)
 	PGPROC	   *proc;
 	SERIALIZABLEXACTTAG sxacttag;
 	SERIALIZABLEXACT *sxact;
-	bool		found;
 	HASHCTL		hash_ctl;
 
 	/* We only do this for serializable transactions.  Once. */
@@ -596,10 +704,8 @@ RegisterSerializableTransaction(const Snapshot snapshot)
 	{
 		Assert(TransactionIdFollows(snapshot->xmin, SerializableGlobalXmin));
 	}
-	sxact = (SERIALIZABLEXACT *) hash_search(SerializableXactHash,
-											 &sxacttag,
-											 HASH_ENTER, &found);
-	Assert(!found);
+	sxact = CreatePredTran();
+	/* TODO SSI: If null, cancel oldest tran and try again? */
 	if (!sxact)
 		ereport(ERROR,
 				(errcode(ERRCODE_OUT_OF_MEMORY),
@@ -607,6 +713,7 @@ RegisterSerializableTransaction(const Snapshot snapshot)
 				 errhint("You might need to increase max_predicate_locks_per_transaction.")));
 
 	/* Initialize the structure. */
+	sxact->tag = sxacttag;
 	sxact->outConflict = InvalidSerializableXact;
 	sxact->inConflict = InvalidSerializableXact;
 	sxact->topXid = GetTopTransactionIdIfAny();
@@ -1542,13 +1649,12 @@ PredicateLockPageCombine(const Relation relation, const BlockNumber oldblkno,
 static void
 SetNewSerializableGlobalXmin(void)
 {
-	HASH_SEQ_STATUS seqstat;
 	SERIALIZABLEXACT *sxact;
 
 	SerializableGlobalXmin = InvalidTransactionId;
 	SerializableGlobalXminCount = 0;
-	hash_seq_init(&seqstat, SerializableXactHash);
-	while ((sxact = (SERIALIZABLEXACT *) hash_seq_search(&seqstat)))
+
+	for (sxact = FirstPredTran(); sxact != NULL; sxact = NextPredTran(sxact))
 	{
 		if (!SxactIsOnFinishedList(sxact))
 		{
@@ -1662,7 +1768,6 @@ ReleasePredicateLocks(const bool isCommit)
 		ClearOldPredicateLocks();
 
 	MySerializableXact = InvalidSerializableXact;
-	MyXid = InvalidTransactionId;
 
 	/* Delete per-transaction lock table */
 	hash_destroy(LocalPredicateLockHash);
@@ -1777,7 +1882,7 @@ ReleaseOneSerializableXact(SERIALIZABLEXACT *sxact)
 	LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
 	if (sxidtag.xid != InvalidTransactionId)
 		hash_search(SerializableXidHash, &sxidtag, HASH_REMOVE, NULL);
-	hash_search(SerializableXactHash, &(sxact->tag), HASH_REMOVE, NULL);
+	ReleasePredTran(sxact);
 	LWLockRelease(SerializableXactHashLock);
 }
 
@@ -1838,7 +1943,6 @@ CheckForSerializableConflictOut(const bool valid, const Relation relation,
 	TransactionId xid;
 	SERIALIZABLEXIDTAG sxidtag;
 	SERIALIZABLEXID *sxid;
-	SERIALIZABLEXACTTAG sxacttag;
 	SERIALIZABLEXACT *sxact;
 
 	if (SkipSerialization(relation))
@@ -1922,18 +2026,18 @@ CheckForSerializableConflictOut(const bool valid, const Relation relation,
 		return;
 	}
 
-	sxacttag = sxact->tag;
 	LWLockRelease(SerializableXactHashLock);
 
 	LWLockAcquire(SerializableXactHashLock, LW_EXCLUSIVE);
-	sxact = (SERIALIZABLEXACT *)
-		hash_search(SerializableXactHash, &sxacttag, HASH_FIND, NULL);
-	if (!sxact)
+	sxid = (SERIALIZABLEXID *)
+		hash_search(SerializableXidHash, &sxidtag, HASH_FIND, NULL);
+	if (!sxid)
 	{
 		/* It must have been cleaned up, which means it wasn't useful. */
 		LWLockRelease(SerializableXactHashLock);
 		return;
 	}
+	Assert(sxid->myXact == sxact);
 	xid = sxact->topXid;
 	if (!XidIsConcurrent(xid))
 	{
diff --git a/src/include/storage/predicate_internal.h b/src/include/storage/predicate_internal.h
index d6a2b8c..222fc74 100644
--- a/src/include/storage/predicate_internal.h
+++ b/src/include/storage/predicate_internal.h
@@ -80,6 +80,38 @@ typedef struct SERIALIZABLEXACT
 								 * cleanup */
 } SERIALIZABLEXACT;
 
+/*
+ * The following types are used to provide an ad hoc list for holding
+ * SERIALIZABLEXACT objects.  An HTAB is overkill, since there is no need to
+ * access these by key -- there are direct pointers to these objects where
+ * needed.  If a shared memory list is created, these types can probably be
+ * eliminated in favor of using the general solution.
+ */
+typedef struct PredTranListElementData
+{
+	SHM_QUEUE	link;
+	SERIALIZABLEXACT	sxact;
+} PredTranListElementData;
+
+typedef struct PredTranListElementData * PredTranListElement;
+
+#define PredTranListElementDataSize \
+		((Size)MAXALIGN(sizeof(PredTranListElementData)))
+
+typedef struct PredTranListData
+{
+	SHM_QUEUE	availableList;
+	SHM_QUEUE	activeList;
+	PredTranListElement	element;
+	int	entryLimit;
+	int entryCount;
+} PredTranListData;
+
+typedef struct PredTranListData *PredTranList;
+
+#define PredTranListDataSize \
+		((Size)MAXALIGN(sizeof(PredTranListData)))
+
 
 /*
  * The SERIALIZABLEXIDTAG struct identifies an xid assigned to a serializable
-- 
1.6.3.3