Rewrite the FSM. Instead of relying on a fixed-size shared memory segment, the

free space information is stored in a dedicated FSM relation fork, with each
relation (except for hash indexes; they don't use FSM).

This eliminates the max_fsm_relations and max_fsm_pages GUC options; remove any
trace of them from the backend, initdb, and documentation.

Rewrite contrib/pg_freespacemap to match the new FSM implementation. Also
introduce a new variant of the get_raw_page(regclass, int4, int4) function in
contrib/pageinspect that let's you to return pages from any relation fork, and
a new fsm_page_contents() function to inspect the new FSM pages.

1 files changed, 25 insertions, 55 deletions

diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 64a719f8279..abb6bd5c5d4 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -12,7 +12,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/access/nbtree/nbtree.c,v 1.161 2008/06/19 00:46:03 alvherre Exp $
+ *	  $PostgreSQL: pgsql/src/backend/access/nbtree/nbtree.c,v 1.162 2008/09/30 10:52:10 heikki Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -26,6 +26,7 @@
 #include "miscadmin.h"
 #include "storage/bufmgr.h"
 #include "storage/freespace.h"
+#include "storage/indexfsm.h"
 #include "storage/ipc.h"
 #include "storage/lmgr.h"
 #include "utils/memutils.h"
@@ -56,9 +57,7 @@ typedef struct
 	IndexBulkDeleteCallback callback;
 	void	   *callback_state;
 	BTCycleId	cycleid;
-	BlockNumber *freePages;
-	int			nFreePages;		/* number of entries in freePages[] */
-	int			maxFreePages;	/* allocated size of freePages[] */
+	BlockNumber lastUsedPage;
 	BlockNumber totFreePages;	/* true total # of free pages */
 	MemoryContext pagedelcontext;
 } BTVacState;
@@ -110,6 +109,9 @@ btbuild(PG_FUNCTION_ARGS)
 		elog(ERROR, "index \"%s\" already contains data",
 			 RelationGetRelationName(index));
 
+	/* Initialize FSM */
+	InitIndexFreeSpaceMap(index);
+
 	buildstate.spool = _bt_spoolinit(index, indexInfo->ii_Unique, false);
 
 	/*
@@ -623,9 +625,7 @@ btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
 	vstate.callback = callback;
 	vstate.callback_state = callback_state;
 	vstate.cycleid = cycleid;
-	vstate.freePages = NULL;	/* temporarily */
-	vstate.nFreePages = 0;
-	vstate.maxFreePages = 0;
+	vstate.lastUsedPage = BTREE_METAPAGE;
 	vstate.totFreePages = 0;
 
 	/* Create a temporary memory context to run _bt_pagedel in */
@@ -670,17 +670,6 @@ btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
 		if (needLock)
 			UnlockRelationForExtension(rel, ExclusiveLock);
 
-		/* Allocate freePages after we read num_pages the first time */
-		if (vstate.freePages == NULL)
-		{
-			/* No point in remembering more than MaxFSMPages pages */
-			vstate.maxFreePages = MaxFSMPages;
-			if ((BlockNumber) vstate.maxFreePages > num_pages)
-				vstate.maxFreePages = (int) num_pages;
-			vstate.freePages = (BlockNumber *)
-				palloc(vstate.maxFreePages * sizeof(BlockNumber));
-		}
-
 		/* Quit if we've scanned the whole relation */
 		if (blkno >= num_pages)
 			break;
@@ -697,42 +686,22 @@ btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
 	 * acquiring exclusive lock on the index and then rechecking all the
 	 * pages; doesn't seem worth it.
 	 */
-	if (info->vacuum_full && vstate.nFreePages > 0)
+	if (info->vacuum_full && vstate.lastUsedPage < num_pages - 1)
 	{
-		BlockNumber new_pages = num_pages;
-
-		while (vstate.nFreePages > 0 &&
-			   vstate.freePages[vstate.nFreePages - 1] == new_pages - 1)
-		{
-			new_pages--;
-			stats->pages_deleted--;
-			vstate.nFreePages--;
-			vstate.totFreePages = vstate.nFreePages;	/* can't be more */
-		}
-		if (new_pages != num_pages)
-		{
-			/*
-			 * Okay to truncate.
-			 */
-			RelationTruncate(rel, new_pages);
+		BlockNumber new_pages = vstate.lastUsedPage + 1;
 
-			/* update statistics */
-			stats->pages_removed += num_pages - new_pages;
+		/*
+		 * Okay to truncate.
+		 */
+		FreeSpaceMapTruncateRel(rel, new_pages);
+		RelationTruncate(rel, new_pages);
 
-			num_pages = new_pages;
-		}
+		/* update statistics */
+		stats->pages_removed += num_pages - new_pages;
+		vstate.totFreePages -= (num_pages - new_pages);
+		num_pages = new_pages;
 	}
 
-	/*
-	 * Update the shared Free Space Map with the info we now have about free
-	 * pages in the index, discarding any old info the map may have. We do not
-	 * need to sort the page numbers; they're in order already.
-	 */
-	RecordIndexFreeSpace(&rel->rd_node, vstate.totFreePages,
-						 vstate.nFreePages, vstate.freePages);
-
-	pfree(vstate.freePages);
-
 	MemoryContextDelete(vstate.pagedelcontext);
 
 	/* update statistics */
@@ -788,8 +757,7 @@ restart:
 	/*
 	 * If we are recursing, the only case we want to do anything with is a
 	 * live leaf page having the current vacuum cycle ID.  Any other state
-	 * implies we already saw the page (eg, deleted it as being empty). In
-	 * particular, we don't want to risk adding it to freePages twice.
+	 * implies we already saw the page (eg, deleted it as being empty).
 	 */
 	if (blkno != orig_blkno)
 	{
@@ -803,12 +771,15 @@ restart:
 		}
 	}
 
+	/* If the page is in use, update lastUsedPage */
+	if (!_bt_page_recyclable(page) && vstate->lastUsedPage < blkno)
+		vstate->lastUsedPage = blkno;
+
 	/* Page is valid, see what to do with it */
 	if (_bt_page_recyclable(page))
 	{
 		/* Okay to recycle this page */
-		if (vstate->nFreePages < vstate->maxFreePages)
-			vstate->freePages[vstate->nFreePages++] = blkno;
+		RecordFreeIndexPage(rel, blkno);
 		vstate->totFreePages++;
 		stats->pages_deleted++;
 	}
@@ -944,8 +915,7 @@ restart:
 		 */
 		if (ndel && info->vacuum_full)
 		{
-			if (vstate->nFreePages < vstate->maxFreePages)
-				vstate->freePages[vstate->nFreePages++] = blkno;
+			RecordFreeIndexPage(rel, blkno);
 			vstate->totFreePages++;
 		}