Add a caching option to dump. Use -C. Note that NetBSD has a caching option

called -r but it takes 512 byte blocks instead of megabytes, and I felt a
megabytes specification would be far more useful so I did not use the same
option character.

This will *greatly* improve dump performance at the cost of possibly
missing filesystem changes that occur between passes, and does a fairly
good job making up for the loss of buffered block devices.  Caching is disabled
by default to retain historical behavior.

In tests, dump performance improved by about 40% when dumping / or /usr.

Beware that dump forks and the cache may wind up being larger then you
specify, but a more complex shared memory implementation would not produce
results that are all that much better so I kept it simple for now.

MFC after:	3 days

6 files changed, 175 insertions, 6 deletions

diff --git a/sbin/dump/Makefile b/sbin/dump/Makefile
index 1148d8f..58b5951 100644
--- a/sbin/dump/Makefile
+++ b/sbin/dump/Makefile
@@ -18,7 +18,7 @@ LINKS=	${BINDIR}/dump ${BINDIR}/rdump
 CFLAGS+=-DRDUMP
 CFLAGS+=-I${.CURDIR}/../../libexec/rlogind
 WARNS=	0
-SRCS=	itime.c main.c optr.c dumprmt.c tape.c traverse.c unctime.c
+SRCS=	itime.c main.c optr.c dumprmt.c tape.c traverse.c unctime.c cache.c
 MAN=	dump.8
 MLINKS+=dump.8 rdump.8
 
diff --git a/sbin/dump/cache.c b/sbin/dump/cache.c
new file mode 100644
index 0000000..c049466
--- /dev/null
+++ b/sbin/dump/cache.c
@@ -0,0 +1,151 @@
+/*
+ * CACHE.C
+ *
+ *	Block cache for dump
+ *
+ * $FreeBSD$
+ */
+
+#include <sys/param.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+
+#ifdef sunos
+#include <sys/vnode.h>
+
+#include <ufs/fs.h>
+#include <ufs/fsdir.h>
+#include <ufs/inode.h>
+#else
+#include <ufs/ufs/dir.h>
+#include <ufs/ufs/dinode.h>
+#include <ufs/ffs/fs.h>
+#endif
+
+#include <protocols/dumprestore.h>
+
+#include <ctype.h>
+#include <stdio.h>
+#ifdef __STDC__
+#include <errno.h>
+#include <string.h>
+#include <stdlib.h>
+#include <unistd.h>
+#endif
+#include "dump.h"
+
+typedef struct Block {
+	struct Block	*b_HNext;	/* must be first field */
+	off_t		b_Offset;
+	char		*b_Data;
+} Block;
+
+#define HFACTOR		4
+#define BLKFACTOR	4
+
+static char  *DataBase;
+static Block **BlockHash;
+static int   BlockSize;
+static int   HSize;
+static int   NBlocks;
+
+static void
+cinit(void)
+{
+	int i;
+	int hi;
+	Block *base;
+
+	if ((BlockSize = sblock->fs_bsize * BLKFACTOR) > MAXBSIZE)
+		BlockSize = MAXBSIZE;
+	NBlocks = cachesize / BlockSize;
+	HSize = NBlocks / HFACTOR;
+
+	msg("Cache %d MB, blocksize = %d\n", 
+	    NBlocks * BlockSize / (1024 * 1024), BlockSize);
+
+	base = calloc(sizeof(Block), NBlocks);
+	BlockHash = calloc(sizeof(Block *), HSize);
+	DataBase = mmap(NULL, NBlocks * BlockSize, 
+			PROT_READ|PROT_WRITE, MAP_ANON, -1, 0);
+	for (i = 0; i < NBlocks; ++i) {
+		base[i].b_Data = DataBase + i * BlockSize;
+		base[i].b_Offset = (off_t)-1;
+		hi = i / HFACTOR;
+		base[i].b_HNext = BlockHash[hi];
+		BlockHash[hi] = &base[i];
+	}
+}
+
+ssize_t
+cread(int fd, void *buf, size_t nbytes, off_t offset)
+{
+	Block *blk;
+	Block **pblk;
+	Block **ppblk;
+	int hi;
+	int n;
+	off_t mask;
+
+	/*
+	 * If the cache is disabled, revert to pread.  If the
+	 * cache has not been initialized, initialize the cache.
+	 */
+	if (sblock->fs_bsize && DataBase == NULL) {
+		if (cachesize <= 0)
+			return(pread(fd, buf, nbytes, offset));
+		cinit();
+	}
+
+	/*
+	 * If the request crosses a cache block boundary, or the
+	 * request is larger or equal to the cache block size,
+	 * revert to pread().  Full-block-reads are typically
+	 * one-time calls and caching would be detrimental.
+	 */
+	mask = ~(off_t)(BlockSize - 1);
+	if (nbytes >= BlockSize ||
+	    ((offset ^ (offset + nbytes - 1)) & mask) != 0) {
+		return(pread(fd, buf, nbytes, offset));
+	}
+
+	/*
+	 * Obtain and access the cache block.  Cache a successful
+	 * result.  If an error occurs, revert to pread() (this might
+	 * occur near the end of the media).
+	 */
+	hi = (offset / BlockSize) % HSize;
+	pblk = &BlockHash[hi];
+	ppblk = NULL;
+	while ((blk = *pblk) != NULL) {
+		if (((blk->b_Offset ^ offset) & mask) == 0) {
+#if 0
+			fprintf(stderr, "%08llx %d (%08x)\n", offset, nbytes, 
+			    sblock->fs_size * sblock->fs_fsize);
+#endif
+			break;
+		}
+		ppblk = pblk;
+		pblk = &blk->b_HNext;
+	}
+	if (blk == NULL) {
+		blk = *ppblk;
+		pblk = ppblk;
+		blk->b_Offset = offset & mask;
+		n = pread(fd, blk->b_Data, BlockSize, blk->b_Offset);
+		if (n != BlockSize) {
+			blk->b_Offset = (off_t)-1;
+			blk = NULL;
+		}
+	}
+	if (blk) {
+		bcopy(blk->b_Data + (offset - blk->b_Offset), buf, nbytes);
+		*pblk = blk->b_HNext;
+		blk->b_HNext = BlockHash[hi];
+		BlockHash[hi] = blk;
+		return(nbytes);
+	} else {
+		return(pread(fd, buf, nbytes, offset));
+	}
+}
+
diff --git a/sbin/dump/dump.8 b/sbin/dump/dump.8
index 23beca3..424e4b3 100644
--- a/sbin/dump/dump.8
+++ b/sbin/dump/dump.8
@@ -46,6 +46,7 @@
 .Op Fl B Ar records
 .Op Fl b Ar blocksize
 .Op Fl D Ar dumpdates
+.Op Fl C Ar cachesize
 .Op Fl d Ar density
 .Op Fl f Ar file
 .Op Fl h Ar level
@@ -142,6 +143,16 @@ Specify an alternate path to the
 file.
 The default is
 .Pa /etc/dumpdates .
+.It Fl C Ar cachesize
+Specify the cache size in megabytes.  This will greatly improve performance
+at the cost of
+.Nm
+possibly not noticing changes in the filesystem between passes.  It is
+recommended that you always use this option when dumping a snapshot.
+Beware that
+.Nm
+forks, and the actual memory use may be larger then the specified cache
+size.  The recommended cache size is between 8 and 32 (megabytes).
 .It Fl d Ar density
 Set tape density to
 .Ar density .
diff --git a/sbin/dump/dump.h b/sbin/dump/dump.h
index eb04b0c..feb5913 100644
--- a/sbin/dump/dump.h
+++ b/sbin/dump/dump.h
@@ -77,6 +77,7 @@ long	asize;		/* number of 0.1" units written on current tape */
 int	etapes;		/* estimated number of tapes */
 int	nonodump;	/* if set, do not honor UF_NODUMP user flags */
 int	unlimited;	/* if set, write to end of medium */
+int	cachesize;	/* size of block cache in bytes */
 
 int	notify;		/* notify operator flag */
 int	blockswritten;	/* number of blocks written on current tape */
diff --git a/sbin/dump/main.c b/sbin/dump/main.c
index 34223b1..7fcf112 100644
--- a/sbin/dump/main.c
+++ b/sbin/dump/main.c
@@ -82,6 +82,7 @@ int	density = 0;	/* density in bytes/0.1" " <- this is for hilit19 */
 int	ntrec = NTREC;	/* # tape blocks in each tape record */
 int	cartridge = 0;	/* Assume non-cartridge tape */
 int	dokerberos = 0;	/* Use Kerberos authentication */
+int	cachesize = 0;	/* block cache size (in bytes), defaults to 0 */
 long	dev_bsize = 1;	/* recalculated below */
 long	blocksperfile;	/* output blocks per file */
 char	*host = NULL;	/* remote host (if any) */
@@ -127,9 +128,9 @@ main(int argc, char *argv[])
 
 	obsolete(&argc, &argv);
 #ifdef KERBEROS
-#define optstring "0123456789aB:b:cd:f:h:kLns:ST:uWwD:"
+#define optstring "0123456789aB:b:cd:f:h:kLns:ST:uWwD:C:"
 #else
-#define optstring "0123456789aB:b:cd:f:h:Lns:ST:uWwD:"
+#define optstring "0123456789aB:b:cd:f:h:Lns:ST:uWwD:C:"
 #endif
 	while ((ch = getopt(argc, argv, optstring)) != -1)
 #undef optstring
@@ -172,6 +173,10 @@ main(int argc, char *argv[])
 			dumpdates = optarg;
 			break;
 
+		case 'C':
+			cachesize = numarg("cachesize", 0, 0) * 1024 * 1024;
+			break;
+
 		case 'h':
 			honorlevel = numarg("honor level", 0L, 10L);
 			break;
diff --git a/sbin/dump/traverse.c b/sbin/dump/traverse.c
index ab2ee71..ec0d56e 100644
--- a/sbin/dump/traverse.c
+++ b/sbin/dump/traverse.c
@@ -739,8 +739,8 @@ bread(ufs2_daddr_t blkno, char *buf, int size)
 	int cnt, i;
 
 loop:
-	if ((cnt = pread(diskfd, buf, size, ((off_t)blkno << dev_bshift))) ==
-						size)
+	cnt = cread(diskfd, buf, size, ((off_t)blkno << dev_bshift));
+	if (cnt == size)
 		return;
 	if (blkno + (size / dev_bsize) > fsbtodb(sblock, sblock->fs_size)) {
 		/*
@@ -774,7 +774,8 @@ loop:
 			breaderrors = 0;
 	}
 	/*
-	 * Zero buffer, then try to read each sector of buffer separately.
+	 * Zero buffer, then try to read each sector of buffer separately,
+	 * and bypass the cache.
 	 */
 	memset(buf, 0, size);
 	for (i = 0; i < size; i += dev_bsize, buf += dev_bsize, blkno++) {