pg_basebackup from cascading standby after timeline switch

diff --git a/src/backend/replication/basebackup.c b/src/backend/replication/basebackup.c
index 65200c1..5c0deaa 100644
--- a/src/backend/replication/basebackup.c
+++ b/src/backend/replication/basebackup.c
@@ -12,12 +12,13 @@
  */
 #include "postgres.h"
 
+#include <string.h>
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <unistd.h>
 #include <time.h>
 
-#include "access/xlog_internal.h"		/* for pg_start/stop_backup */
+#include "access/xlog_internal.h"
 #include "catalog/pg_type.h"
 #include "lib/stringinfo.h"
 #include "libpq/libpq.h"
@@ -44,6 +45,7 @@ typedef struct
 
 
 static int64 sendDir(char *path, int basepathlen, bool sizeonly);
+static void sendTimeLineHistoryFiles(void);
 static void sendFile(char *readfilename, char *tarfilename,
 		 struct stat * statbuf);
 static void sendFileWithContent(const char *filename, const char *content);
@@ -286,6 +288,27 @@ perform_base_backup(basebackup_options *opt, DIR *tblspcdir)
 				break;
 		}
 
+		/*
+		 * Include all timeline history files.
+		 *
+		 * The timeline history files are usually not strictly required to
+		 * restore the backup, but if you take a backup from a standby server,
+		 * and the WAL segment containing the checkpoint record contains WAL
+		 * from an older timeline, recovery will complain on the older
+		 * timeline's ID if there is no timeline history file listing it. This
+		 * can happen if you take a backup right after promoting a standby to
+		 * become new master, and take the backup from a different, cascading
+		 * standby server.
+		 *
+		 * However, even when not strictly required, the timeline history
+		 * files are tiny, and provide a lot of forensic information about the
+		 * recovery history of the database, so it's best to always include
+		 * them all. (If asked to include WAL, that is. Otherwise you need a
+		 * WAL archive to restore anyway, and the timeline history files
+		 * should be present in the archive)
+		 */
+		sendTimeLineHistoryFiles();
+
 		/* Send CopyDone message for the last tar file */
 		pq_putemptymessage('c');
 	}
@@ -726,6 +749,58 @@ sendDir(char *path, int basepathlen, bool sizeonly)
 	return size;
 }
 
+/*
+ * Include all timeline history files from pg_xlog in the output tar stream.
+ */
+static void
+sendTimeLineHistoryFiles(void)
+{
+	DIR		   *dir;
+	struct dirent *de;
+	char		pathbuf[MAXPGPATH];
+	struct stat statbuf;
+
+	dir = AllocateDir("./pg_xlog");
+	while ((de = ReadDir(dir, "./pg_xlog")) != NULL)
+	{
+		CHECK_FOR_INTERRUPTS();
+
+		if (strlen(de->d_name) == 8 + strlen(".history") &&
+			strspn(de->d_name, "0123456789ABCDEF") == 8 &&
+			strcmp(de->d_name + 8, ".history") == 0)
+		{
+			/* It looks like a timeline history file. Include it. */
+			snprintf(pathbuf, MAXPGPATH, "./pg_xlog/%s", de->d_name);
+
+			if (lstat(pathbuf, &statbuf) != 0)
+			{
+				if (errno != ENOENT)
+					ereport(ERROR,
+							(errcode_for_file_access(),
+							 errmsg("could not stat file or directory \"%s\": %m",
+									pathbuf)));
+
+				/* If the file went away while scanning, it's no error. */
+				continue;
+			}
+
+			if (!S_ISREG(statbuf.st_mode))
+			{
+				/*
+				 * Huh? It's named like a timeline history file, but isn't a
+				 * regular file.
+				 */
+				ereport(WARNING,
+						(errmsg("skipping special file \"%s\"", pathbuf)));
+				continue;
+			}
+
+			sendFile(pathbuf, pathbuf + 1, &statbuf);
+		}
+	}
+	FreeDir(dir);
+}
+
 /*****
  * Functions for handling tar file format
  *

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index c847913..060dc08 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -2675,6 +2675,7 @@ XLogFileReadAnyTLI(XLogSegNo segno, int emode, int source)
 	char		path[MAXPGPATH];
 	ListCell   *cell;
 	int			fd;
+	List	   *tles;
 
 	/*
 	 * Loop looking for a suitable timeline ID: we might need to read any of
@@ -2685,8 +2686,21 @@ XLogFileReadAnyTLI(XLogSegNo segno, int emode, int source)
 	 * to go backwards; this prevents us from picking up the wrong file when a
 	 * parent timeline extends to higher segment numbers than the child we
 	 * want to read.
-	 */
-	foreach(cell, expectedTLEs)
+	 *
+	 * If we haven't read the timeline history file yet, we don't know which
+	 * TLIs to scan, so read it now. We don't save the list in expectedTLEs,
+	 * however, unless we actually find a valid segment. That way if there is
+	 * neither timeline history file nor WAL segment in the archive, and
+	 * streaming replication is set up, we'll read the timeline history file
+	 * streamed from the master when we start streaming, instead of recovering
+	 * with a dummy history generated here.
+	 */
+	if (expectedTLEs)
+		tles = expectedTLEs;
+	else
+		tles = readTimeLineHistory(recoveryTargetTLI);
+
+	foreach(cell, tles)
 	{
 		TimeLineID	tli = ((TimeLineHistoryEntry *) lfirst(cell))->tli;
 
@@ -2699,6 +2713,8 @@ XLogFileReadAnyTLI(XLogSegNo segno, int emode, int source)
 			if (fd != -1)
 			{
 				elog(DEBUG1, "got WAL segment from archive");
+				if (!expectedTLEs)
+					expectedTLEs = tles;
 				return fd;
 			}
 		}
@@ -2707,7 +2723,11 @@ XLogFileReadAnyTLI(XLogSegNo segno, int emode, int source)
 		{
 			fd = XLogFileRead(segno, emode, tli, XLOG_FROM_PG_XLOG, true);
 			if (fd != -1)
+			{
+				if (!expectedTLEs)
+					expectedTLEs = tles;
 				return fd;
+			}
 		}
 	}
 
@@ -5279,49 +5299,6 @@ StartupXLOG(void)
 	 */
 	readRecoveryCommandFile();
 
-	/* Now we can determine the list of expected TLIs */
-	expectedTLEs = readTimeLineHistory(recoveryTargetTLI);
-
-	/*
-	 * If the location of the checkpoint record is not on the expected
-	 * timeline in the history of the requested timeline, we cannot proceed:
-	 * the backup is not part of the history of the requested timeline.
-	 */
-	if (tliOfPointInHistory(ControlFile->checkPoint, expectedTLEs) !=
-			ControlFile->checkPointCopy.ThisTimeLineID)
-	{
-		XLogRecPtr switchpoint;
-
-		/*
-		 * tliSwitchPoint will throw an error if the checkpoint's timeline
-		 * is not in expectedTLEs at all.
-		 */
-		switchpoint = tliSwitchPoint(ControlFile->checkPointCopy.ThisTimeLineID, expectedTLEs);
-		ereport(FATAL,
-				(errmsg("requested timeline %u is not a child of this server's history",
-						recoveryTargetTLI),
-				 errdetail("Latest checkpoint is at %X/%X on timeline %u, but in the history of the requested timeline, the server forked off from that timeline at %X/%X",
-						   (uint32) (ControlFile->checkPoint >> 32),
-						   (uint32) ControlFile->checkPoint,
-						   ControlFile->checkPointCopy.ThisTimeLineID,
-						   (uint32) (switchpoint >> 32),
-						   (uint32) switchpoint)));
-	}
-
-	/*
-	 * The min recovery point should be part of the requested timeline's
-	 * history, too.
-	 */
-	if (!XLogRecPtrIsInvalid(ControlFile->minRecoveryPoint) &&
-		tliOfPointInHistory(ControlFile->minRecoveryPoint - 1, expectedTLEs) !=
-			ControlFile->minRecoveryPointTLI)
-		ereport(FATAL,
-				(errmsg("requested timeline %u does not contain minimum recovery point %X/%X on timeline %u",
-						recoveryTargetTLI,
-						(uint32) (ControlFile->minRecoveryPoint >> 32),
-						(uint32) ControlFile->minRecoveryPoint,
-						ControlFile->minRecoveryPointTLI)));
-
 	/*
 	 * Save archive_cleanup_command in shared memory so that other processes
 	 * can see it.
@@ -5443,6 +5420,47 @@ StartupXLOG(void)
 		wasShutdown = (record->xl_info == XLOG_CHECKPOINT_SHUTDOWN);
 	}
 
+	/*
+	 * If the location of the checkpoint record is not on the expected
+	 * timeline in the history of the requested timeline, we cannot proceed:
+	 * the backup is not part of the history of the requested timeline.
+	 */
+	Assert(expectedTLEs); /* was initialized by reading checkpoint record */
+	if (tliOfPointInHistory(checkPointLoc, expectedTLEs) !=
+			checkPoint.ThisTimeLineID)
+	{
+		XLogRecPtr switchpoint;
+
+		/*
+		 * tliSwitchPoint will throw an error if the checkpoint's timeline
+		 * is not in expectedTLEs at all.
+		 */
+		switchpoint = tliSwitchPoint(ControlFile->checkPointCopy.ThisTimeLineID, expectedTLEs);
+		ereport(FATAL,
+				(errmsg("requested timeline %u is not a child of this server's history",
+						recoveryTargetTLI),
+				 errdetail("Latest checkpoint is at %X/%X on timeline %u, but in the history of the requested timeline, the server forked off from that timeline at %X/%X",
+						   (uint32) (ControlFile->checkPoint >> 32),
+						   (uint32) ControlFile->checkPoint,
+						   ControlFile->checkPointCopy.ThisTimeLineID,
+						   (uint32) (switchpoint >> 32),
+						   (uint32) switchpoint)));
+	}
+
+	/*
+	 * The min recovery point should be part of the requested timeline's
+	 * history, too.
+	 */
+	if (!XLogRecPtrIsInvalid(ControlFile->minRecoveryPoint) &&
+		tliOfPointInHistory(ControlFile->minRecoveryPoint - 1, expectedTLEs) !=
+			ControlFile->minRecoveryPointTLI)
+		ereport(FATAL,
+				(errmsg("requested timeline %u does not contain minimum recovery point %X/%X on timeline %u",
+						recoveryTargetTLI,
+						(uint32) (ControlFile->minRecoveryPoint >> 32),
+						(uint32) ControlFile->minRecoveryPoint,
+						ControlFile->minRecoveryPointTLI)));
+
 	LastRec = RecPtr = checkPointLoc;
 
 	ereport(DEBUG1,
@@ -9569,13 +9587,24 @@ WaitForWALToBecomeAvailable(XLogRecPtr RecPtr, bool randAccess,
 					 */
 					if (PrimaryConnInfo)
 					{
-						XLogRecPtr ptr = fetching_ckpt ? RedoStartLSN : RecPtr;
-						TimeLineID tli = tliOfPointInHistory(ptr, expectedTLEs);
+						XLogRecPtr ptr;
+						TimeLineID tli;
 
-						if (curFileTLI > 0 && tli < curFileTLI)
-							elog(ERROR, "according to history file, WAL location %X/%X belongs to timeline %u, but previous recovered WAL file came from timeline %u",
-								 (uint32) (ptr >> 32), (uint32) ptr,
-								 tli, curFileTLI);
+						if (fetching_ckpt)
+						{
+							ptr = RedoStartLSN;
+							tli = ControlFile->checkPointCopy.ThisTimeLineID;
+						}
+						else
+						{
+							ptr = RecPtr;
+							tli = tliOfPointInHistory(ptr, expectedTLEs);
+
+							if (curFileTLI > 0 && tli < curFileTLI)
+								elog(ERROR, "according to history file, WAL location %X/%X belongs to timeline %u, but previous recovered WAL file came from timeline %u",
+									 (uint32) (ptr >> 32), (uint32) ptr,
+									 tli, curFileTLI);
+						}
 						curFileTLI = tli;
 						RequestXLogStreaming(curFileTLI, ptr, PrimaryConnInfo);
 					}
@@ -9739,11 +9768,16 @@ WaitForWALToBecomeAvailable(XLogRecPtr RecPtr, bool randAccess,
 				{
 					/*
 					 * Great, streamed far enough.  Open the file if it's not
-					 * open already.  Use XLOG_FROM_STREAM so that source info
-					 * is set correctly and XLogReceiptTime isn't changed.
+					 * open already.  Also read the timeline history file if
+					 * we haven't initialized timeline history yet; it should
+					 * be streamed over and present in pg_xlog by now.  Use
+					 * XLOG_FROM_STREAM so that source info is set correctly
+					 * and XLogReceiptTime isn't changed.
 					 */
 					if (readFile < 0)
 					{
+						if (!expectedTLEs)
+							expectedTLEs = readTimeLineHistory(receiveTLI);
 						readFile = XLogFileRead(readSegNo, PANIC,
 												receiveTLI,
 												XLOG_FROM_STREAM, false);
diff --git a/src/backend/replication/walreceiver.c b/src/backend/replication/walreceiver.c
index 326c313..99280d8 100644
--- a/src/backend/replication/walreceiver.c
+++ b/src/backend/replication/walreceiver.c
@@ -338,7 +338,7 @@ WalReceiverMain(void)
 		 * ensure that a unique timeline id is chosen in every case, but let's
 		 * avoid the confusion of timeline id collisions where we can.
 		 */
-		WalRcvFetchTimeLineHistoryFiles(startpointTLI + 1, primaryTLI);
+		WalRcvFetchTimeLineHistoryFiles(startpointTLI, primaryTLI);
 
 		/*
 		 * Start streaming.
@@ -627,7 +627,7 @@ WalRcvFetchTimeLineHistoryFiles(TimeLineID first, TimeLineID last)
 
 	for (tli = first; tli <= last; tli++)
 	{
-		if (!existsTimeLineHistory(tli))
+		if (tli != 1 && !existsTimeLineHistory(tli))
 		{
 			char	   *fname;
 			char	   *content;

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index 6f352fd..30d877b 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -3456,19 +3456,36 @@ PreallocXlogFiles(XLogRecPtr endptr)
 }
 
 /*
- * Get the log/seg of the latest removed or recycled WAL segment.
- * Returns 0/0 if no WAL segments have been removed since startup.
+ * Throws an error if the given log segment has already been removed or
+ * recycled. The caller should only pass a segment that it knows to have
+ * existed while the server has been running, as this function always
+ * succeeds if no WAL segments have been removed since startup.
+ * 'tli' is only used in the error message.
  */
 void
-XLogGetLastRemoved(uint32 *log, uint32 *seg)
+CheckXLogRemoved(uint32 log, uint32 seg, TimeLineID tli)
 {
 	/* use volatile pointer to prevent code rearrangement */
 	volatile XLogCtlData *xlogctl = XLogCtl;
+	uint32		lastRemovedLog,
+				lastRemovedSeg;
 
 	SpinLockAcquire(&xlogctl->info_lck);
-	*log = xlogctl->lastRemovedLog;
-	*seg = xlogctl->lastRemovedSeg;
+	lastRemovedLog = xlogctl->lastRemovedLog;
+	lastRemovedSeg = xlogctl->lastRemovedSeg;
 	SpinLockRelease(&xlogctl->info_lck);
+
+	if (log < lastRemovedLog ||
+		(log == lastRemovedLog && seg <= lastRemovedSeg))
+	{
+		char		filename[MAXFNAMELEN];
+
+		XLogFileName(filename, tli, log, seg);
+		ereport(ERROR,
+				(errcode_for_file_access(),
+				 errmsg("requested WAL segment %s has already been removed",
+						filename)));
+	}
 }
 
 /*
diff --git a/src/backend/replication/basebackup.c b/src/backend/replication/basebackup.c
index bc95215..3f46bfc 100644
--- a/src/backend/replication/basebackup.c
+++ b/src/backend/replication/basebackup.c
@@ -55,11 +55,10 @@ static void base_backup_cleanup(int code, Datum arg);
 static void perform_base_backup(basebackup_options *opt, DIR *tblspcdir);
 static void parse_basebackup_options(List *options, basebackup_options *opt);
 static void SendXlogRecPtrResult(XLogRecPtr ptr);
+static int compareWalFileNames(const void *a, const void *b);
 
 /*
  * Size of each block sent into the tar stream for larger files.
- *
- * XLogSegSize *MUST* be evenly dividable by this
  */
 #define TAR_SEND_SIZE 32768
 
@@ -219,70 +218,203 @@ perform_base_backup(basebackup_options *opt, DIR *tblspcdir)
 	{
 		/*
 		 * We've left the last tar file "open", so we can now append the
-		 * required WAL files to it.
+		 * required WAL files to it. I'd rather not worry about timelines
+		 * here, so include WAL files belonging to any timeline, as long as
+		 * it's in the right WAL range, between 'startptr' and 'endptr'.
 		 */
+		char		pathbuf[MAXPGPATH];
 		uint32		logid,
 					logseg;
+		uint32		startlogid,
+					startlogseg;
 		uint32		endlogid,
 					endlogseg;
 		struct stat statbuf;
+		List	   *historyFileList = NIL;
+		List	   *walFileList = NIL;
+		char	  **walFiles;
+		int			nWalFiles;
+		char		firstoff[MAXFNAMELEN];
+		char		lastoff[MAXFNAMELEN];
+		DIR		   *dir;
+		struct dirent *de;
+		int			i;
+		ListCell   *lc;
+		TimeLineID	tli;
 
-		MemSet(&statbuf, 0, sizeof(statbuf));
-		statbuf.st_mode = S_IRUSR | S_IWUSR;
-#ifndef WIN32
-		statbuf.st_uid = geteuid();
-		statbuf.st_gid = getegid();
-#endif
-		statbuf.st_size = XLogSegSize;
-		statbuf.st_mtime = time(NULL);
-
-		XLByteToSeg(startptr, logid, logseg);
+		XLByteToSeg(startptr, startlogid, startlogseg);
+		XLogFileName(firstoff, ThisTimeLineID, startlogid, startlogseg);
 		XLByteToPrevSeg(endptr, endlogid, endlogseg);
-
-		while (true)
+		XLogFileName(lastoff, ThisTimeLineID, endlogid, endlogseg);
+		/* Read list of eligible WAL files into an array */
+		dir = AllocateDir("pg_xlog");
+		if (!dir)
+			ereport(ERROR,
+					(errmsg("could not open directory \"%s\": %m", "pg_xlog")));
+		while ((de = ReadDir(dir, "pg_xlog")) != NULL)
 		{
-			/* Send another xlog segment */
-			char		fn[MAXPGPATH];
-			int			i;
+			/* Does it look like a WAL segment, and is it in the range? */
+			if (strlen(de->d_name) == 24 &&
+				strspn(de->d_name, "0123456789ABCDEF") == 24 &&
+				strcmp(de->d_name + 8, firstoff + 8) >= 0 &&
+				strcmp(de->d_name + 8, lastoff + 8) <= 0)
+			{
+				walFileList = lappend(walFileList, pstrdup(de->d_name));
+			}
+			/* Does it look like a timeline history file? */
+			else if (strlen(de->d_name) == 8 + strlen(".history") &&
+					 strspn(de->d_name, "0123456789ABCDEF") == 8 &&
+					 strcmp(de->d_name + 8, ".history") == 0)
+			{
+				historyFileList = lappend(historyFileList, pstrdup(de->d_name));
+			}
+		}
+		FreeDir(dir);
 
-			XLogFilePath(fn, ThisTimeLineID, logid, logseg);
-			_tarWriteHeader(fn, NULL, &statbuf);
+		/*
+		 * Before we go any further, check that none of the WAL segments we
+		 * need were removed.
+		 */
+		CheckXLogRemoved(startlogid, startlogseg, ThisTimeLineID);
+
+		/*
+		 * Put the WAL filenames into an array, and sort. We send the files
+		 * in order from oldest to newest, to reduce the chance that a file
+		 * is recycled before we get a chance to send it over.
+		 */
+		nWalFiles = list_length(walFileList);
+		walFiles = palloc(nWalFiles * sizeof(char *));
+		i = 0;
+		foreach(lc, walFileList)
+		{
+			walFiles[i++] = lfirst(lc);
+		}
+		qsort(walFiles, nWalFiles, sizeof(char *), compareWalFileNames);
 
-			/* Send the actual WAL file contents, block-by-block */
-			for (i = 0; i < XLogSegSize / TAR_SEND_SIZE; i++)
+		/*
+		 * Sanity check: the first and last segment should include startptr
+		 * and endptr, with no gaps in between.
+		 */
+		XLogFromFileName(walFiles[0], &tli, &logid, &logseg);
+		if (logid != startlogid || logseg != startlogseg)
+		{
+			char startfname[MAXFNAMELEN];
+			XLogFileName(startfname, ThisTimeLineID, startlogid, startlogseg);
+			ereport(ERROR,
+					(errmsg("could not find WAL file %s", startfname)));
+		}
+		for (i = 0; i < nWalFiles; i++)
+		{
+			int		currlogid = logid,
+					currlogseg = logseg;
+			int		nextlogid = logid,
+					nextlogseg = logseg;
+			NextLogSeg(nextlogid, nextlogseg);
+
+			XLogFromFileName(walFiles[i], &tli, &logid, &logseg);
+			if (!((nextlogid == logid && nextlogseg == logseg) ||
+				  (currlogid == logid && currlogseg == logseg)))
 			{
-				char		buf[TAR_SEND_SIZE];
-				XLogRecPtr	ptr;
+				char nextfname[MAXFNAMELEN];
+				XLogFileName(nextfname, ThisTimeLineID, nextlogid, nextlogseg);
+				ereport(ERROR,
+						(errmsg("could not find WAL file %s", nextfname)));
+			}
+		}
+		if (logid != endlogid || logseg != endlogseg)
+		{
+			char endfname[MAXFNAMELEN];
+			XLogFileName(endfname, ThisTimeLineID, endlogid, endlogseg);
+			ereport(ERROR,
+					(errmsg("could not find WAL file %s", endfname)));
+		}
 
-				ptr.xlogid = logid;
-				ptr.xrecoff = logseg * XLogSegSize + TAR_SEND_SIZE * i;
+		/* Ok, we have everything we need. Send the WAL files. */
+		for (i = 0; i < nWalFiles; i++)
+		{
+			FILE	   *fp;
+			char		buf[TAR_SEND_SIZE];
+			size_t		cnt;
+			pgoff_t		len = 0;
+
+			snprintf(pathbuf, MAXPGPATH, "./pg_xlog/%s", walFiles[i]);
+			XLogFromFileName(walFiles[i], &tli, &logid, &logseg);
 
+			fp = AllocateFile(pathbuf, "rb");
+			if (fp == NULL)
+			{
 				/*
-				 * Some old compilers, e.g. gcc 2.95.3/x86, think that passing
-				 * a struct in the same function as a longjump might clobber a
-				 * variable.  bjm 2011-02-04
-				 * http://lists.apple.com/archives/xcode-users/2003/Dec//msg000
-				 * 51.html
+				 * Most likely reason for this is that the file was already
+				 * removed by a checkpoint, so check for that to get a better
+				 * error message.
 				 */
-				XLogRead(buf, ptr, TAR_SEND_SIZE);
-				if (pq_putmessage('d', buf, TAR_SEND_SIZE))
+				CheckXLogRemoved(logid, logseg, tli);
+
+				ereport(ERROR,
+						(errcode_for_file_access(),
+						 errmsg("could not open file \"%s\": %m", pathbuf)));
+			}
+
+			if (fstat(fileno(fp), &statbuf) != 0)
+				ereport(ERROR,
+						(errcode_for_file_access(),
+						 errmsg("could not stat file \"%s\": %m",
+								pathbuf)));
+			if (statbuf.st_size != XLogSegSize)
+			{
+				CheckXLogRemoved(logid, logseg, tli);
+				ereport(ERROR,
+						(errcode_for_file_access(),
+						 errmsg("unexpected WAL file size \"%s\"", walFiles[i])));
+			}
+
+			_tarWriteHeader(pathbuf + 1, NULL, &statbuf);
+
+			while ((cnt = fread(buf, 1, Min(sizeof(buf), XLogSegSize - len), fp)) > 0)
+			{
+				CheckXLogRemoved(logid, logseg, tli);
+				/* Send the chunk as a CopyData message */
+				if (pq_putmessage('d', buf, cnt))
 					ereport(ERROR,
 							(errmsg("base backup could not send data, aborting backup")));
+
+				len += cnt;
+				if (len == XLogSegSize)
+					break;
 			}
 
-			/*
-			 * Files are always fixed size, and always end on a 512 byte
-			 * boundary, so padding is never necessary.
-			 */
+			if (len != XLogSegSize)
+			{
+				CheckXLogRemoved(logid, logseg, tli);
+				ereport(ERROR,
+						(errcode_for_file_access(),
+						 errmsg("unexpected WAL file size \"%s\"", walFiles[i])));
+			}
 
+			/* XLogSegSize is a multiple of 512, so no need for padding */
+			FreeFile(fp);
+		}
 
-			/* Advance to the next WAL file */
-			NextLogSeg(logid, logseg);
+		/*
+		 * Send timeline history files too. Only the latest timeline history
+		 * file is required for recovery, and even that only if there happens
+		 * to be a timeline switch in the first WAL segment that contains the
+		 * checkpoint record, or if we're taking a base backup from a standby
+		 * server and the target timeline changes while the backup is taken. 
+		 * But they are small and highly useful for debugging purposes, so
+		 * better include them all, always.
+		 */
+		foreach(lc, historyFileList)
+		{
+			char *fname = lfirst(lc);
+			snprintf(pathbuf, MAXPGPATH, "./pg_xlog/%s", fname);
 
-			/* Have we reached our stop position yet? */
-			if (logid > endlogid ||
-				(logid == endlogid && logseg > endlogseg))
-				break;
+			if (lstat(pathbuf, &statbuf) != 0)
+				ereport(ERROR,
+						(errcode_for_file_access(),
+						 errmsg("could not stat file \"%s\": %m", pathbuf)));
+
+			sendFile(pathbuf, pathbuf + 1, &statbuf, false);
 		}
 
 		/* Send CopyDone message for the last tar file */
@@ -292,6 +424,19 @@ perform_base_backup(basebackup_options *opt, DIR *tblspcdir)
 }
 
 /*
+ * qsort comparison function, to compare log/seg portion of WAL segment
+ * filenames, ignoring the timeline portion.
+ */
+static int
+compareWalFileNames(const void *a, const void *b)
+{
+	char *fna = *((char **) a);
+	char *fnb = *((char **) b);
+
+	return strcmp(fna + 8, fnb + 8);
+}
+
+/*
  * Parse the base backup options passed down by the parser
  */
 static void
diff --git a/src/backend/replication/walsender.c b/src/backend/replication/walsender.c
index 6c27449..5c93146 100644
--- a/src/backend/replication/walsender.c
+++ b/src/backend/replication/walsender.c
@@ -977,8 +977,6 @@ XLogRead(char *buf, XLogRecPtr startptr, Size count)
 	char	   *p;
 	XLogRecPtr	recptr;
 	Size		nbytes;
-	uint32		lastRemovedLog;
-	uint32		lastRemovedSeg;
 	uint32		log;
 	uint32		seg;
 
@@ -1073,19 +1071,8 @@ retry:
 	 * read() succeeds in that case, but the data we tried to read might
 	 * already have been overwritten with new WAL records.
 	 */
-	XLogGetLastRemoved(&lastRemovedLog, &lastRemovedSeg);
 	XLByteToSeg(startptr, log, seg);
-	if (log < lastRemovedLog ||
-		(log == lastRemovedLog && seg <= lastRemovedSeg))
-	{
-		char		filename[MAXFNAMELEN];
-
-		XLogFileName(filename, ThisTimeLineID, log, seg);
-		ereport(ERROR,
-				(errcode_for_file_access(),
-				 errmsg("requested WAL segment %s has already been removed",
-						filename)));
-	}
+	CheckXLogRemoved(log, seg, ThisTimeLineID);
 
 	/*
 	 * During recovery, the currently-open WAL file might be replaced with the
diff --git a/src/include/access/xlog.h b/src/include/access/xlog.h
index ecd3f0f..c21e43a 100644
--- a/src/include/access/xlog.h
+++ b/src/include/access/xlog.h
@@ -275,7 +275,7 @@ extern int XLogFileInit(uint32 log, uint32 seg,
 extern int	XLogFileOpen(uint32 log, uint32 seg);
 
 
-extern void XLogGetLastRemoved(uint32 *log, uint32 *seg);
+extern void CheckXLogRemoved(uint32 log, uint32 seg, TimeLineID tli);
 extern void XLogSetAsyncXactLSN(XLogRecPtr record);
 
 extern Buffer RestoreBackupBlock(XLogRecPtr lsn, XLogRecord *record,