lockfree-getbuffer.v2.patch

diff --git a/src/backend/storage/buffer/freelist.c b/src/backend/storage/buffer/freelist.c
index 76a4bec..c08378c 100644
--- a/src/backend/storage/buffer/freelist.c
+++ b/src/backend/storage/buffer/freelist.c
@@ -15,10 +15,10 @@
  */
 #include "postgres.h"
 
+#include "storage/atomic.h"
 #include "storage/buf_internals.h"
 #include "storage/bufmgr.h"
 
-
 /*
  * The shared freelist control information.
  */
@@ -27,14 +27,7 @@ typedef struct
 	/* Clock sweep hand: index of next buffer to consider grabbing */
 	int			nextVictimBuffer;
 
-	int			firstFreeBuffer;	/* Head of list of unused buffers */
-	int			lastFreeBuffer; /* Tail of list of unused buffers */
-
-	/*
-	 * NOTE: lastFreeBuffer is undefined when firstFreeBuffer is -1 (that is,
-	 * when the list is empty)
-	 */
-
+	int			padding1[15]; 		/* Ensure a separate cache line */
 	/*
 	 * Statistics.	These counters should be wide enough that they can't
 	 * overflow during a single bgwriter cycle.
@@ -42,15 +35,21 @@ typedef struct
 	uint32		completePasses; /* Complete cycles of the clock sweep */
 	uint32		numBufferAllocs;	/* Buffers allocated since last reset */
 
+	int			padding2[14];		/* Ensure a separate cache line */
+
 	/*
 	 * Notification latch, or NULL if none.  See StrategyNotifyBgWriter.
 	 */
 	Latch	   *bgwriterLatch;
+	int			firstFreeBuffer;	/* Head of list of unused buffers */
 } BufferStrategyControl;
 
 /* Pointers to shared state */
 static BufferStrategyControl *StrategyControl = NULL;
 
+#define BUF_ALLOC_STATS_GRANULARITY 16
+static int		localBufferAllocs = 0;
+
 /*
  * Private (non-shared) state for managing a ring of shared buffers to re-use.
  * This is currently the only kind of BufferAccessStrategy object, but someday
@@ -114,7 +113,9 @@ StrategyGetBuffer(BufferAccessStrategy strategy, bool *lock_held)
 	volatile BufferDesc *buf;
 	Latch	   *bgwriterLatch;
 	int			trycounter;
+	int			victim;
 
+	*lock_held = false;
 	/*
 	 * If given a strategy object, see whether it can select a buffer. We
 	 * assume strategy objects don't need the BufFreelistLock.
@@ -124,43 +125,51 @@ StrategyGetBuffer(BufferAccessStrategy strategy, bool *lock_held)
 		buf = GetBufferFromRing(strategy);
 		if (buf != NULL)
 		{
-			*lock_held = false;
 			return buf;
 		}
 	}
 
-	/* Nope, so lock the freelist */
-	*lock_held = true;
-	LWLockAcquire(BufFreelistLock, LW_EXCLUSIVE);
 
 	/*
 	 * We count buffer allocation requests so that the bgwriter can estimate
 	 * the rate of buffer consumption.	Note that buffers recycled by a
 	 * strategy object are intentionally not counted here.
 	 */
-	StrategyControl->numBufferAllocs++;
+	localBufferAllocs++;
+	if (localBufferAllocs == BUF_ALLOC_STATS_GRANULARITY)
+	{
+		pg_atomic_add(StrategyControl->numBufferAllocs, BUF_ALLOC_STATS_GRANULARITY);
+		localBufferAllocs = 0;
+	}
 
 	/*
-	 * If bgwriterLatch is set, we need to waken the bgwriter, but we should
-	 * not do so while holding BufFreelistLock; so release and re-grab.  This
-	 * is annoyingly tedious, but it happens at most once per bgwriter cycle,
-	 * so the performance hit is minimal.
+	 * If bgwriterLatch is set, we need to waken the bgwriter. Bgwriter needs
+	 * to see our allocation to not go to sleep again so we emit a write
+	 * barrier. Because this happens at most once per bgwriter cycle, the
+	 * performance hit is minimal.
 	 */
-	bgwriterLatch = StrategyControl->bgwriterLatch;
-	if (bgwriterLatch)
+	if (StrategyControl->bgwriterLatch)
 	{
-		StrategyControl->bgwriterLatch = NULL;
-		LWLockRelease(BufFreelistLock);
+		pg_atomic_fetch_and_set(bgwriterLatch, StrategyControl->bgwriterLatch, NULL);
+		if (bgwriterLatch)
 		SetLatch(bgwriterLatch);
-		LWLockAcquire(BufFreelistLock, LW_EXCLUSIVE);
 	}
-
 	/*
 	 * Try to get a buffer from the freelist.  Note that the freeNext fields
 	 * are considered to be protected by the BufFreelistLock not the
 	 * individual buffer spinlocks, so it's OK to manipulate them without
 	 * holding the spinlock.
 	 */
+	if (StrategyControl->firstFreeBuffer >= 0)
+	{
+		/*
+		 * There might be something in the freelist, so lock and check
+		 * again */
+		*lock_held = true;
+		LWLockAcquire(BufFreelistLock, LW_EXCLUSIVE);
+		/*
+		 * XXX Need to avoid reusing value fetched before lock here,
+		 * volatile access required? Output from GCC 4.6 says no. */
 	while (StrategyControl->firstFreeBuffer >= 0)
 	{
 		buf = &BufferDescriptors[StrategyControl->firstFreeBuffer];
@@ -187,17 +196,33 @@ StrategyGetBuffer(BufferAccessStrategy strategy, bool *lock_held)
 		UnlockBufHdr(buf);
 	}
 
+		LWLockRelease(BufFreelistLock);
+		*lock_held = false;
+	}
+
 	/* Nothing on the freelist, so run the "clock sweep" algorithm */
 	trycounter = NBuffers;
 	for (;;)
 	{
-		buf = &BufferDescriptors[StrategyControl->nextVictimBuffer];
-
-		if (++StrategyControl->nextVictimBuffer >= NBuffers)
+		pg_atomic_fetch_and_add(victim, StrategyControl->nextVictimBuffer, 1);
+		/*
+		 * If we just incremented the value past the wrapping point
+		 * emit a correcting subtraction and account for the pass.
+		 */
+		if (victim == NBuffers-1)
 		{
-			StrategyControl->nextVictimBuffer = 0;
-			StrategyControl->completePasses++;
+			pg_atomic_sub(StrategyControl->nextVictimBuffer, NBuffers);
+			pg_atomic_inc(StrategyControl->completePasses);
 		}
+		/*
+		 * Do the modulus operation asynchronously in case the value had
+		 * overflowed. */
+		while (victim >= NBuffers)
+			victim -= NBuffers;
+
+		Assert(victim < NBuffers && victim >= 0);
+
+		buf = &BufferDescriptors[victim];
 
 		/*
 		 * If the buffer is pinned or has a nonzero usage_count, we cannot use
@@ -253,8 +278,6 @@ StrategyFreeBuffer(volatile BufferDesc *buf)
 	if (buf->freeNext == FREENEXT_NOT_IN_LIST)
 	{
 		buf->freeNext = StrategyControl->firstFreeBuffer;
-		if (buf->freeNext < 0)
-			StrategyControl->lastFreeBuffer = buf->buf_id;
 		StrategyControl->firstFreeBuffer = buf->buf_id;
 	}
 
@@ -277,16 +300,17 @@ StrategySyncStart(uint32 *complete_passes, uint32 *num_buf_alloc)
 {
 	int			result;
 
-	LWLockAcquire(BufFreelistLock, LW_EXCLUSIVE);
 	result = StrategyControl->nextVictimBuffer;
+	while (result >= NBuffers)
+		result -= NBuffers;
+
 	if (complete_passes)
 		*complete_passes = StrategyControl->completePasses;
 	if (num_buf_alloc)
 	{
-		*num_buf_alloc = StrategyControl->numBufferAllocs;
-		StrategyControl->numBufferAllocs = 0;
+		pg_atomic_fetch_and_set(*num_buf_alloc,
+			StrategyControl->numBufferAllocs, 0);
 	}
-	LWLockRelease(BufFreelistLock);
 	return result;
 }
 
@@ -306,9 +330,7 @@ StrategyNotifyBgWriter(Latch *bgwriterLatch)
 	 * atomic to StrategyGetBuffer.  The bgwriter should call this rather
 	 * infrequently, so there's no performance penalty from being safe.
 	 */
-	LWLockAcquire(BufFreelistLock, LW_EXCLUSIVE);
 	StrategyControl->bgwriterLatch = bgwriterLatch;
-	LWLockRelease(BufFreelistLock);
 }
 
 
@@ -378,7 +400,6 @@ StrategyInitialize(bool init)
 		 * assume it was previously set up by InitBufferPool().
 		 */
 		StrategyControl->firstFreeBuffer = 0;
-		StrategyControl->lastFreeBuffer = NBuffers - 1;
 
 		/* Initialize the clock sweep pointer */
 		StrategyControl->nextVictimBuffer = 0;
diff --git a/src/include/storage/atomic.h b/src/include/storage/atomic.h
new file mode 100644
index 0000000..147c75a
--- /dev/null
+++ b/src/include/storage/atomic.h
@@ -0,0 +1,66 @@
+/*-------------------------------------------------------------------------
+ *
+ * atomic.h
+ *	  Atomic memory operations.
+ *
+ * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/storage/atomic.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef ATOMIC_H
+#define ATOMIC_H
+
+#include "storage/barrier.h"
+
+#if defined(__GNUC__)
+
+#define pg_atomic_fetch_and_add(dst, src, value) \
+	do { dst = __sync_fetch_and_add(&(src), (value)); } while(0)
+
+#define pg_atomic_add(var, value) \
+	do { __sync_fetch_and_add(&(var), (value)); } while(0)
+
+#define pg_atomic_sub(var, value) \
+	do { __sync_fetch_and_sub(&(var), (value)); } while(0)
+
+#define pg_atomic_inc(var) do { __sync_fetch_and_add(&(var), 1); } while(0)
+
+#define pg_atomic_fetch_and_set(dst, src, value) \
+	do { dst = __sync_lock_test_and_set(&(src), (value)); } while (0)
+
+#endif
+
+#if !defined(pg_atomic_fetch_and_add)
+#define pg_atomic_fetch_and_add(dst, src, value) \
+	do { S_LOCK(&dummy_spinlock); \
+	dst = src; \
+	src += value; \
+	S_UNLOCK(&dummy_spinlock); } while (0)
+#endif
+
+#if !defined(pg_atomic_sub)
+#define pg_atomic_sub(var, value) \
+	do { S_LOCK(&dummy_spinlock); \
+	var -= value; \
+	S_UNLOCK(&dummy_spinlock); } while (0)
+#endif
+
+#if !defined(pg_atomic_inc)
+#define pg_atomic_inc(var) \
+	do { S_LOCK(&dummy_spinlock); \
+	var++; \
+	S_UNLOCK(&dummy_spinlock); } while (0)
+#endif
+
+#if !defined(pg_atomic_fetch_and_set)
+#define pg_atomic_fetch_and_set(dst, src, value) \
+	do { S_LOCK(&dummy_spinlock); \
+	dst = src; \
+	src = value; \
+	S_UNLOCK(&dummy_spinlock); } while (0)
+#endif
+
+#endif   /* ATOMIC_H */