Implement a simple LRU block cache. By default this is initialised to 16k,

and will bypass transfers for more than 8k.  Blocks are invalidated after
2 seconds, so removable media should not confuse the cache.

The 8k threshold is a compromise; all UFS transfers performed by
libstand are 8k or less, so large file reads thrash the cache.
However many filesystem metadata operations are also performed using
8k blocks, so using a lower threshold gives poor performance.

Those of you with an eye for cache algorithms are welcome to tell me
how badly this one sucks; you can start with the 'bcachestats' command
which will print the contents of the cache and access statistics.

3 files changed, 241 insertions, 4 deletions

diff --git a/sys/boot/common/Makefile.inc b/sys/boot/common/Makefile.inc
index 805b009..d8e6e6d 100644
--- a/sys/boot/common/Makefile.inc
+++ b/sys/boot/common/Makefile.inc
@@ -1,7 +1,8 @@
-# $Id: Makefile.inc,v 1.5 1998/09/14 18:27:04 msmith Exp $
+# $Id: Makefile.inc,v 1.6 1998/09/30 19:38:26 peter Exp $
 
-SRCS+=	boot.c commands.c console.c devopen.c interp.c interp_backslash.c
-SRCS+=	interp_parse.c load_aout.c load_elf.c ls.c misc.c module.c panic.c
+SRCS+=	bcache.c boot.c commands.c console.c devopen.c interp.c 
+SRCS+=	interp_backslash.c interp_parse.c load_aout.c load_elf.c ls.c misc.c 
+SRCS+=	module.c panic.c
 
 # Machine-independant ISA PnP
 .if HAVE_ISABUS
diff --git a/sys/boot/common/bcache.c b/sys/boot/common/bcache.c
new file mode 100644
index 0000000..93a117f
--- /dev/null
+++ b/sys/boot/common/bcache.c
@@ -0,0 +1,227 @@
+/*
+ * mjs copyright
+ */
+
+/*
+ * Simple LRU block cache
+ */
+
+#include <stand.h>
+#include <string.h>
+#include <bitstring.h>
+
+#include "bootstrap.h"
+
+/* #define BCACHE_DEBUG */
+
+#ifdef BCACHE_DEBUG
+#define BCACHE_TIMEOUT	10
+# define DEBUG(fmt, args...)	printf("%s: " fmt "\n" , __FUNCTION__ , ## args)
+#else
+#define BCACHE_TIMEOUT	2
+# define DEBUG(fmt, args...)
+#endif
+
+
+struct bcachectl
+{
+    daddr_t	bc_blkno;
+    time_t	bc_stamp;
+};
+
+static struct bcachectl	*bcache_ctl;
+static caddr_t		bcache_data;
+static bitstr_t		*bcache_miss;
+static int		bcache_nblks;
+static int		bcache_blksize;
+static int		bcache_hits, bcache_misses, bcache_ops, bcache_bypasses;
+
+static void	bcache_insert(caddr_t buf, daddr_t blkno);
+static int	bcache_lookup(caddr_t buf, daddr_t blkno);
+
+/*
+ * Initialise the cache for (nblks) of (bsize).
+ */
+int
+bcache_init(int nblks, size_t bsize)
+{
+    int		i;
+
+    /* discard any old contents */
+    if (bcache_data != NULL) {
+	free(bcache_data);
+	bcache_data = NULL;
+	free(bcache_ctl);
+    }
+
+    /* Allocate control structures */
+    bcache_nblks = nblks;
+    bcache_blksize = bsize;
+    bcache_data = malloc(bcache_nblks * bcache_blksize);
+    bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl));
+    bcache_miss = bit_alloc((bcache_nblks + 1) / 2);
+    if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) {
+	if (bcache_miss)
+	    free(bcache_miss);
+	if (bcache_ctl)
+	    free(bcache_ctl);
+	if (bcache_data)
+	    free(bcache_data);
+	bcache_data = NULL;
+	return(ENOMEM);
+    }
+
+    /* Invalidate the cache */
+    for (i = 0; i < bcache_nblks; i++)
+	bcache_ctl[i].bc_stamp = 0;
+
+    return(0);
+}
+
+/* 
+ * Handle a transfer request; fill in parts of the request that can
+ * be satisfied by the cache, use the supplied strategy routine to do
+ * device I/O and then use the I/O results to populate the cache. 
+ *
+ * Requests larger than 1/2 the cache size will be bypassed and go
+ * directly to the disk.  XXX tune this.
+ */
+int
+bcache_strategy(void *devdata, int rw, daddr_t blk, size_t size, void *buf, size_t *rsize)
+{
+    struct bcache_devdata	*dd = (struct bcache_devdata *)devdata;
+    int				nblk, p_size;
+    daddr_t			p_blk;
+    caddr_t			p_buf;
+    int				i, j, result;
+
+    bcache_ops++;
+    
+    /* bypass large requests, or when the cache is inactive */
+    if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) {
+	DEBUG("bypass %d from %d", size / bcache_blksize, blk);
+	bcache_bypasses++;
+	return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize));
+    }
+
+    nblk = size / bcache_blksize;
+    result = 0;
+
+    /* Satisfy any cache hits up front */
+    for (i = 0; i < nblk; i++) {
+	if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) {
+	    bit_set(bcache_miss, i);	/* cache miss */
+	    bcache_misses++;
+	} else {
+	    bit_clear(bcache_miss, i);	/* cache hit */
+	    bcache_hits++;
+	}
+    }
+
+    /* Go back and fill in any misses  XXX optimise */
+    p_blk = -1;
+    p_buf = NULL;
+    p_size = 0;
+    for (i = 0; i < nblk; i++) {
+	if (bit_test(bcache_miss, i)) {
+	    /* miss, add to pending transfer */
+	    if (p_blk == -1) {
+		p_blk = blk + i;
+		p_buf = buf + (bcache_blksize * i);
+		p_size = 1;
+	    } else {
+		p_size++;
+	    }
+	} else if (p_blk != -1) {
+	    /* hit, complete pending transfer */
+	    result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
+	    if (result != 0)
+		goto done;
+	    for (j = 0; j < p_size; j++)
+		bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
+	    p_blk = -1;
+	}
+    }
+    if (p_blk != -1) {
+	/* pending transfer left */
+	result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
+	if (result != 0)
+	    goto done;
+	for (j = 0; j < p_size; j++)
+	    bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
+    }
+    
+ done:
+    if ((result == 0) && (rsize != NULL))
+	*rsize = size;
+    return(result);
+}
+
+
+/*
+ * Insert a block into the cache.  Retire the oldest block to do so, if required.
+ */
+static void
+bcache_insert(caddr_t buf, daddr_t blkno) 
+{
+    time_t	now;
+    int		i, cand;
+    
+    time(&now);
+
+    /* find the oldest block */
+    for (cand = 0, i = 1; i < bcache_nblks; i++) {
+	if (bcache_ctl[i].bc_blkno == blkno) {
+	    /* reuse old entry */
+	    cand = i;
+	    break;
+	}
+	if (bcache_ctl[i].bc_stamp < now)
+	    cand = i;
+    }
+    
+    DEBUG("insert blk %d -> %d @ %d", blkno, cand, now);
+    bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize);
+    bcache_ctl[cand].bc_blkno = blkno;
+    bcache_ctl[cand].bc_stamp = now;
+}
+
+/*
+ * Look for a block in the cache.  Blocks more than BCACHE_TIMEOUT seconds old
+ *  may be stale (removable media) and thus are discarded.  Copy the block out 
+ * if successful and return zero, or return nonzero on failure.
+ */
+static int
+bcache_lookup(caddr_t buf, daddr_t blkno)
+{
+    time_t	now;
+    int		i;
+    
+    time(&now);
+
+    for (i = 0; i < bcache_nblks; i++)
+	/* cache hit? */
+	if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) {
+	    bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize);
+	    DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp);
+	    return(0);
+	}
+    return(ENOENT);
+}
+
+COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache);
+
+static int
+command_bcache(int argc, char *argv[])
+{
+    int		i;
+    
+    for (i = 0; i < bcache_nblks; i++) {
+	printf("  %02x: %08x %04x", i, bcache_ctl[i].bc_blkno, bcache_ctl[i].bc_stamp & 0xffff);
+	if (((i + 1) % 4) == 0)
+	    printf("\n");
+    }
+    printf("\n%d ops  %d bypasses  %d hits  %d misses\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses);
+    return(CMD_OK);
+}
+
diff --git a/sys/boot/common/bootstrap.h b/sys/boot/common/bootstrap.h
index 2eb1d80..a373e35 100644
--- a/sys/boot/common/bootstrap.h
+++ b/sys/boot/common/bootstrap.h
@@ -23,7 +23,7 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- *	$Id: bootstrap.h,v 1.14 1998/10/21 20:07:04 msmith Exp $
+ *	$Id: bootstrap.h,v 1.15 1998/10/22 20:20:50 msmith Exp $
  */
 
 #include <sys/types.h>
@@ -72,6 +72,15 @@ extern size_t	strlenout(vm_offset_t str);
 extern char	*strdupout(vm_offset_t str);
 
 /*
+ * Disk block cache
+ */
+struct bcache_devdata
+{
+    int         (*dv_strategy)(void *devdata, int rw, daddr_t blk, size_t size, void *buf, size_t *rsize);
+    void	*dv_devdata;
+};
+
+/*
  * Modular console support.
  */
 struct console