diff options
author | msmith <msmith@FreeBSD.org> | 1998-11-02 23:28:11 +0000 |
---|---|---|
committer | msmith <msmith@FreeBSD.org> | 1998-11-02 23:28:11 +0000 |
commit | 7ff854a690d0b1907eb91aa8563be0d65545984d (patch) | |
tree | 4b5368009c1e11ed85475d58f2f379071897c96a /sys/boot | |
parent | 459dfe3332e2fac684dc0f5ce1af023d9101c0b0 (diff) | |
download | FreeBSD-src-7ff854a690d0b1907eb91aa8563be0d65545984d.zip FreeBSD-src-7ff854a690d0b1907eb91aa8563be0d65545984d.tar.gz |
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.
Diffstat (limited to 'sys/boot')
-rw-r--r-- | sys/boot/alpha/common/main.c | 7 | ||||
-rw-r--r-- | sys/boot/alpha/libalpha/srmdisk.c | 19 | ||||
-rw-r--r-- | sys/boot/common/Makefile.inc | 7 | ||||
-rw-r--r-- | sys/boot/common/bcache.c | 227 | ||||
-rw-r--r-- | sys/boot/common/bootstrap.h | 11 | ||||
-rw-r--r-- | sys/boot/i386/libi386/biosdisk.c | 13 | ||||
-rw-r--r-- | sys/boot/i386/loader/main.c | 7 |
7 files changed, 278 insertions, 13 deletions
diff --git a/sys/boot/alpha/common/main.c b/sys/boot/alpha/common/main.c index 2776b08..4140024 100644 --- a/sys/boot/alpha/common/main.c +++ b/sys/boot/alpha/common/main.c @@ -24,7 +24,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $Id: main.c,v 1.7 1998/10/24 00:31:21 msmith Exp $ + * $Id: main.c,v 1.8 1998/10/31 17:12:32 dfr Exp $ */ @@ -142,6 +142,11 @@ main(void) OSFpal(); /* + * Initialise the block cache + */ + bcache_init(32, 512); /* 16k XXX tune this */ + + /* * March through the device switch probing for things. */ for (i = 0; devsw[i] != NULL; i++) diff --git a/sys/boot/alpha/libalpha/srmdisk.c b/sys/boot/alpha/libalpha/srmdisk.c index bd74ba7..f071e15 100644 --- a/sys/boot/alpha/libalpha/srmdisk.c +++ b/sys/boot/alpha/libalpha/srmdisk.c @@ -24,7 +24,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $Id: srmdisk.c,v 1.1.1.1 1998/08/21 03:17:42 msmith Exp $ + * $Id: srmdisk.c,v 1.2 1998/10/31 17:12:32 dfr Exp $ */ /* @@ -61,6 +61,7 @@ static int bd_init(void); static int bd_strategy(void *devdata, int flag, daddr_t dblk, size_t size, void *buf, size_t *rsize); +static int bd_realstrategy(void *devdata, int flag, daddr_t dblk, size_t size, void *buf, size_t *rsize); static int bd_open(struct open_file *f, void *vdev); static int bd_close(struct open_file *f); static void bd_print(int verbose); @@ -70,10 +71,6 @@ struct open_disk { int od_unit; /* our unit number */ int od_boff; /* block offset from beginning of SRM disk */ int od_flags; -#define BD_MODEMASK 0x3 -#define BD_MODEINT13 0x0 -#define BD_MODEEDD1 0x1 -#define BD_MODEEDD3 0x2 #define BD_FLOPPY (1<<2) u_char od_buf[BUFSIZE]; /* transfer buffer (do we want/need this?) */ }; @@ -326,7 +323,17 @@ bd_close(struct open_file *f) } static int -bd_strategy(void *devdata, int flag, daddr_t dblk, size_t size, void *buf, size_t *rsize) +bd_strategy(void *devdata, int rw, daddr_t dblk, size_t size, void *buf, size_t *rsize) +{ + struct bcache_devdata bcd; + + bcd.dv_strategy = bd_realstrategy; + bcd.dv_devdata = devdata; + return(bcache_strategy(&bcd, rw, dblk, size, buf, rsize)); +} + +static int +bd_realstrategy(void *devdata, int flag, daddr_t dblk, size_t size, void *buf, size_t *rsize) { prom_return_t ret; struct open_disk *od = (struct open_disk *)devdata; 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 diff --git a/sys/boot/i386/libi386/biosdisk.c b/sys/boot/i386/libi386/biosdisk.c index b4c7769..502d3be 100644 --- a/sys/boot/i386/libi386/biosdisk.c +++ b/sys/boot/i386/libi386/biosdisk.c @@ -23,7 +23,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $Id: biosdisk.c,v 1.15 1998/10/30 07:15:52 luoqi Exp $ + * $Id: biosdisk.c,v 1.16 1998/10/31 02:53:11 msmith Exp $ */ /* @@ -103,6 +103,7 @@ static int bd_int13probe(struct bdinfo *bd); static int bd_init(void); static int bd_strategy(void *devdata, int flag, daddr_t dblk, size_t size, void *buf, size_t *rsize); +static int bd_realstrategy(void *devdata, int flag, daddr_t dblk, size_t size, void *buf, size_t *rsize); static int bd_open(struct open_file *f, ...); static int bd_close(struct open_file *f); static void bd_print(int verbose); @@ -495,6 +496,16 @@ bd_closedisk(struct open_disk *od) static int bd_strategy(void *devdata, int rw, daddr_t dblk, size_t size, void *buf, size_t *rsize) { + struct bcache_devdata bcd; + + bcd.dv_strategy = bd_realstrategy; + bcd.dv_devdata = devdata; + return(bcache_strategy(&bcd, rw, dblk, size, buf, rsize)); +} + +static int +bd_realstrategy(void *devdata, int rw, daddr_t dblk, size_t size, void *buf, size_t *rsize) +{ struct open_disk *od = (struct open_disk *)(((struct i386_devdesc *)devdata)->d_kind.biosdisk.data); int blks; #ifdef BD_SUPPORT_FRAGS diff --git a/sys/boot/i386/loader/main.c b/sys/boot/i386/loader/main.c index 2e0ed80..dfd1bff 100644 --- a/sys/boot/i386/loader/main.c +++ b/sys/boot/i386/loader/main.c @@ -23,7 +23,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $Id: main.c,v 1.12 1998/10/21 20:10:33 msmith Exp $ + * $Id: main.c,v 1.13 1998/10/22 20:23:58 msmith Exp $ */ /* @@ -98,6 +98,11 @@ main(void) cons_probe(); /* + * Initialise the block cache + */ + bcache_init(32, 512); /* 16k cache XXX tune this */ + + /* * March through the device switch probing for things. */ for (i = 0; devsw[i] != NULL; i++) |