From eed8944177eacc4e4296919f691bc4163564d039 Mon Sep 17 00:00:00 2001
From: Robert Haas <rhaas@postgresql.org>
Date: Thu, 26 Jul 2012 12:50:12 -0400
Subject: [PATCH] CHashAddToGarbage

---
 src/backend/utils/hash/chash.c | 56 ++++++++++++++++++++++++++++------
 1 file changed, 46 insertions(+), 10 deletions(-)

diff --git a/src/backend/utils/hash/chash.c b/src/backend/utils/hash/chash.c
index 6893a36d81..0ed2721f51 100644
--- a/src/backend/utils/hash/chash.c
+++ b/src/backend/utils/hash/chash.c
@@ -185,6 +185,7 @@ typedef struct CHashTableData
 
 /* Function prototypes. */
 static CHashPtr CHashAllocate(CHashTable table);
+static void CHashAddToGarbage(CHashTable table, uint32 bucket, CHashPtr c);
 static void CHashImmediateFree(CHashTable table, CHashPtr c);
 static bool CHashRemoveMarked(CHashTable table, uint32 bucket,
 				  CHashPtr *cp, volatile CHashPtr *p);
@@ -609,7 +610,7 @@ retry:
 	if (found)
 	{
 		CHashPtr	cc;
-		bool		needs_cleanup = false;
+		bool		removed = false;
 
 		/*
 		 * Really do the deletion.  Since we've held no lock up to this
@@ -624,22 +625,27 @@ retry:
 		{
 			n->next = CHashPtrMark(cc);
 			if (*p == c)
+			{
 				*p = cc;
-			else
-				needs_cleanup = true;
+				removed = true;
+			}
 		}
 		SpinLockRelease(&table->bucket[bucket].mutex);
 
 		/*
 		 * At this point the deletion is done.  However, it's possible that
-		 * we weren't able to redirect the pointer that formerly addressed the
-		 * deleted item.  If so, rescan the bucket chain and excise any deleted
-		 * items in the chain.  We don't have to worry about not finding it;
-		 * that just means someone else did the work for us.
+		 * someone else did it before we did it, in which case we need to
+		 * return false rather than true.  Also, we may have successfully
+		 * removed the deleted from the linked list, in which case we need to
+		 * add it to the garbage list; or that we failed to do so, in which
+		 * case we need to rescan the list and remove any deleted items we
+		 * find.
 		 */
-		if (needs_cleanup)
+		if (removed)
+			CHashAddToGarbage(table, bucket, c);
+		else
 		{
-			/* XXX */
+			/* XXX Rescan bucket. */
 		}
 	}
 
@@ -792,6 +798,33 @@ CHashAllocate(CHashTable table)
 	}
 }
 
+/*
+ * Add an arena slot to the appropriate garbage list.
+ *
+ * The next garbage collection cycle for the affected bucket will move it
+ * to the free list.  We can't do that immediately because there might be
+ * someone traversing the list who is counting on being able to follow the
+ * next pointer.  It's OK to clobber the hash value, though, since a spurious
+ * failure to match an already-deleted item shouldn't cause any problems;
+ * this is why gcnext can share space with the hash value.
+ */
+static void
+CHashAddToGarbage(CHashTable table, uint32 bucket, CHashPtr c)
+{
+	uint32		garbage_bucket;
+	volatile CHashNode *n;
+	volatile CHashBucket   *garbage;
+
+ 	garbage_bucket = bucket >> table->garbage_shift;
+	n = CHashTableGetNode(table, c);
+	garbage = &table->garbage[garbage_bucket];
+
+	SpinLockAcquire(&garbage->mutex);
+	n->un.gcnext = garbage->head;
+	garbage->head = c;
+	SpinLockRelease(&garbage->mutex);
+}
+
 /*
  * Free an arena slot immediately.
  *
@@ -804,7 +837,7 @@ static void
 CHashImmediateFree(CHashTable table, CHashPtr c)
 {
 	volatile CHashTable vtable = table;
-	volatile CHashNode  *n;
+	volatile CHashNode *n;
 	uint32		f_home = ((uint32) MyBackendId) % table->nfreelists;
 
 	n = CHashTableGetNode(table, c);
@@ -870,6 +903,9 @@ CHashRemoveMarked(CHashTable table, uint32 bucket, CHashPtr *cp,
 		if (retry_needed)
 			return true;
 
+		/* Add c to garbage list. */
+		CHashAddToGarbage(table, bucket, c);
+
 		/* The new target of the pointer may also be delete-marked, so loop. */
 		c = cc;
 	} while (CHashPtrIsMarked(c));
-- 
2.39.5