freelist_ok.v2.patch

diff --git a/src/backend/storage/buffer/freelist.c b/src/backend/storage/buffer/freelist.c
index bf9903b..b2935af 100644
--- a/src/backend/storage/buffer/freelist.c
+++ b/src/backend/storage/buffer/freelist.c
@@ -108,6 +108,8 @@ StrategyGetBuffer(BufferAccessStrategy strategy, bool *lock_held)
 {
 	volatile BufferDesc *buf;
 	int			trycounter;
+	int			freelist_limit;	/* How fast we get less choosy if no victims */
+	int			usage_limit;	/* How choosy we are about our next victim */
 
 	/*
 	 * If given a strategy object, see whether it can select a buffer. We
@@ -167,7 +169,12 @@ StrategyGetBuffer(BufferAccessStrategy strategy, bool *lock_held)
 	}
 
 	/* Nothing on the freelist, so run the "clock sweep" algorithm */
-	trycounter = NBuffers;
+	trycounter = 0;
+
+#define FREELIST_WORST_CASE_LIMIT	16	
+	usage_limit = 0;
+	freelist_limit = FREELIST_WORST_CASE_LIMIT;
+
 	for (;;)
 	{
 		buf = &BufferDescriptors[StrategyControl->nextVictimBuffer];
@@ -179,16 +186,28 @@ StrategyGetBuffer(BufferAccessStrategy strategy, bool *lock_held)
 		}
 
 		/*
-		 * If the buffer is pinned or has a nonzero usage_count, we cannot use
-		 * it; decrement the usage_count (unless pinned) and keep scanning.
+		 * If the buffer is pinned we cannot use it.
+		 *
+		 * We first look for a buffer with usage_count == 0, but limiting out
+		 * search to the first FREELIST_WORST_CASE_LIMIT buffers. We slowly
+		 * get less choosy if the buffers we see are all popular.
+		 *
+		 * This is designed to give O(k) worst case behaviour in cases
+		 * where there are many popular buffers and shared buffers is large,
+		 * which is common since those two siituations are related.
 		 */
 		LockBufHdr(buf);
 		if (buf->refcount == 0)
 		{
-			if (buf->usage_count > 0)
+			if (buf->usage_count > usage_limit)
 			{
 				buf->usage_count--;
-				trycounter = NBuffers;
+				if (trycounter++ > freelist_limit)
+				{
+					trycounter = 0;
+					usage_limit++;
+					freelist_limit *= 2;
+				}
 			}
 			else
 			{
@@ -198,7 +217,7 @@ StrategyGetBuffer(BufferAccessStrategy strategy, bool *lock_held)
 				return buf;
 			}
 		}
-		else if (--trycounter == 0)
+		else if (trycounter++ >= NBuffers)
 		{
 			/*
 			 * We've scanned all the buffers without making any state changes,