diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 1d43b0b..a9bc17a 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -54,6 +54,7 @@
 #include "miscadmin.h"
 #include "pgstat.h"
 #include "storage/bufmgr.h"
+#include "storage/freespace.h"
 #include "storage/lmgr.h"
 #include "storage/procarray.h"
 #include "storage/smgr.h"
@@ -4029,6 +4030,7 @@ heap_xlog_clean(XLogRecPtr lsn, XLogRecord *record, bool clean_move)
 	int			nredirected;
 	int			ndead;
 	int			nunused;
+	Size		freespace;
 
 	if (record->xl_info & XLR_BKP_BLOCK_1)
 		return;
@@ -4068,6 +4070,15 @@ heap_xlog_clean(XLogRecPtr lsn, XLogRecord *record, bool clean_move)
 	PageSetLSN(page, lsn);
 	PageSetTLI(page, ThisTimeLineID);
 	MarkBufferDirty(buffer);
+
+	/*
+	 * update the FSM as well
+	 *
+	 * XXX: We don't get here if the page was restored from full page image
+	 */
+	freespace = PageGetHeapFreeSpace(page);
+	XLogRecordPageWithFreeSpace(xlrec->node, xlrec->block, freespace);
+
 	UnlockReleaseBuffer(buffer);
 }
 
@@ -4212,6 +4223,7 @@ heap_xlog_insert(XLogRecPtr lsn, XLogRecord *record)
 	HeapTupleHeader htup;
 	xl_heap_header xlhdr;
 	uint32		newlen;
+	Size		freespace;
 
 	if (record->xl_info & XLR_BKP_BLOCK_1)
 		return;
@@ -4271,6 +4283,19 @@ heap_xlog_insert(XLogRecPtr lsn, XLogRecord *record)
 	PageSetLSN(page, lsn);
 	PageSetTLI(page, ThisTimeLineID);
 	MarkBufferDirty(buffer);
+
+	/*
+	 * If the page is running low on free space, update the FSM as well.
+	 * Pretty arbitrarily, our definition of low is less than 20%. We can't
+	 * do much better than that without knowing the fill-factor for the table.
+	 *
+	 * XXX: We don't get here if the page was restored from full page image
+	 */
+	freespace = PageGetHeapFreeSpace(page);
+	if (freespace < BLCKSZ / 5)
+		XLogRecordPageWithFreeSpace(xlrec->target.node, 
+									BufferGetBlockNumber(buffer), freespace);
+
 	UnlockReleaseBuffer(buffer);
 }
 
@@ -4296,6 +4321,7 @@ heap_xlog_update(XLogRecPtr lsn, XLogRecord *record, bool move, bool hot_update)
 	xl_heap_header xlhdr;
 	int			hsize;
 	uint32		newlen;
+	Size		freespace;
 
 	if (record->xl_info & XLR_BKP_BLOCK_1)
 	{
@@ -4456,6 +4482,16 @@ newsame:;
 	PageSetLSN(page, lsn);
 	PageSetTLI(page, ThisTimeLineID);
 	MarkBufferDirty(buffer);
+
+	/*
+	 * If the page is running low on free space, update the FSM as well.
+	 * XXX: We don't get here if the page was restored from full page image
+	 */
+	freespace = PageGetHeapFreeSpace(page);
+	if (freespace < BLCKSZ / 5)
+		XLogRecordPageWithFreeSpace(xlrec->target.node,
+									BufferGetBlockNumber(buffer), freespace);
+
 	UnlockReleaseBuffer(buffer);
 }
 
diff --git a/src/backend/storage/freespace/freespace.c b/src/backend/storage/freespace/freespace.c
index 17f733f..7aa72c9 100644
--- a/src/backend/storage/freespace/freespace.c
+++ b/src/backend/storage/freespace/freespace.c
@@ -203,6 +203,51 @@ RecordPageWithFreeSpace(Relation rel, BlockNumber heapBlk, Size spaceAvail)
 }
 
 /*
+ * XLogRecordPageWithFreeSpace - like RecordPageWithFreeSpace, for use in
+ *		WAL replay
+ */
+void
+XLogRecordPageWithFreeSpace(RelFileNode rnode, BlockNumber heapBlk,
+							Size spaceAvail)
+{
+	int			new_cat = fsm_space_avail_to_cat(spaceAvail);
+	FSMAddress	addr;
+	uint16		slot;
+	BlockNumber blkno;
+	Buffer		buf;
+	
+	/* Get the location of the FSM byte representing the heap block */
+	addr = fsm_get_location(heapBlk, &slot);
+	blkno = fsm_logical_to_physical(addr);
+
+	/* If the page doesn't exist already, extend */
+	buf = XLogReadBufferWithFork(rnode, FSM_FORKNUM, blkno, false);
+	if (!BufferIsValid(buf))
+	{
+		/*
+		 * There's no direct way to tell XLogReadBuffer() that it's OK
+		 * if the page doesn't exist. It will log it as an invalid page,
+		 * and error at the end of WAL replay. To avoid that, lie to
+		 * xlogutils.c that the file was in fact truncated, and initialize
+		 * the page.
+		 *
+		 * XXX: Perhaps we should change XLogReadBufferWithFork() so that
+		 * instead of the 'init' boolean argument, make it an an enum so
+		 * that the third state means "silently extend the relation if the
+		 * page doesn't exist".
+		 */
+		XLogTruncateRelation(rnode, FSM_FORKNUM, blkno);
+		buf = XLogReadBufferWithFork(rnode, FSM_FORKNUM, blkno, true);
+		PageInit(BufferGetPage(buf), BLCKSZ, 0);
+	}
+	Assert(BufferIsValid(buf));
+
+	if (fsm_set_avail(BufferGetPage(buf), slot, new_cat))
+		MarkBufferDirty(buf);
+	UnlockReleaseBuffer(buf);
+}
+
+/*
  * GetRecordedFreePage - return the amount of free space on a particular page,
  *		according to the FSM.
  */
diff --git a/src/include/storage/freespace.h b/src/include/storage/freespace.h
index 7a1664f..e17a8d5 100644
--- a/src/include/storage/freespace.h
+++ b/src/include/storage/freespace.h
@@ -27,6 +27,8 @@ extern BlockNumber RecordAndGetPageWithFreeSpace(Relation rel,
 							  Size spaceNeeded);
 extern void RecordPageWithFreeSpace(Relation rel, BlockNumber heapBlk,
 									Size spaceAvail);
+extern void XLogRecordPageWithFreeSpace(RelFileNode rnode, BlockNumber heapBlk,
+										Size spaceAvail);
 
 extern void FreeSpaceMapTruncateRel(Relation rel, BlockNumber nblocks);
 extern void FreeSpaceMapVacuum(Relation rel);