bcache.c revision 40834
140834Smsmith/*
240834Smsmith * mjs copyright
340834Smsmith */
440834Smsmith
540834Smsmith/*
640834Smsmith * Simple LRU block cache
740834Smsmith */
840834Smsmith
940834Smsmith#include <stand.h>
1040834Smsmith#include <string.h>
1140834Smsmith#include <bitstring.h>
1240834Smsmith
1340834Smsmith#include "bootstrap.h"
1440834Smsmith
1540834Smsmith/* #define BCACHE_DEBUG */
1640834Smsmith
1740834Smsmith#ifdef BCACHE_DEBUG
1840834Smsmith#define BCACHE_TIMEOUT	10
1940834Smsmith# define DEBUG(fmt, args...)	printf("%s: " fmt "\n" , __FUNCTION__ , ## args)
2040834Smsmith#else
2140834Smsmith#define BCACHE_TIMEOUT	2
2240834Smsmith# define DEBUG(fmt, args...)
2340834Smsmith#endif
2440834Smsmith
2540834Smsmith
2640834Smsmithstruct bcachectl
2740834Smsmith{
2840834Smsmith    daddr_t	bc_blkno;
2940834Smsmith    time_t	bc_stamp;
3040834Smsmith};
3140834Smsmith
3240834Smsmithstatic struct bcachectl	*bcache_ctl;
3340834Smsmithstatic caddr_t		bcache_data;
3440834Smsmithstatic bitstr_t		*bcache_miss;
3540834Smsmithstatic int		bcache_nblks;
3640834Smsmithstatic int		bcache_blksize;
3740834Smsmithstatic int		bcache_hits, bcache_misses, bcache_ops, bcache_bypasses;
3840834Smsmith
3940834Smsmithstatic void	bcache_insert(caddr_t buf, daddr_t blkno);
4040834Smsmithstatic int	bcache_lookup(caddr_t buf, daddr_t blkno);
4140834Smsmith
4240834Smsmith/*
4340834Smsmith * Initialise the cache for (nblks) of (bsize).
4440834Smsmith */
4540834Smsmithint
4640834Smsmithbcache_init(int nblks, size_t bsize)
4740834Smsmith{
4840834Smsmith    int		i;
4940834Smsmith
5040834Smsmith    /* discard any old contents */
5140834Smsmith    if (bcache_data != NULL) {
5240834Smsmith	free(bcache_data);
5340834Smsmith	bcache_data = NULL;
5440834Smsmith	free(bcache_ctl);
5540834Smsmith    }
5640834Smsmith
5740834Smsmith    /* Allocate control structures */
5840834Smsmith    bcache_nblks = nblks;
5940834Smsmith    bcache_blksize = bsize;
6040834Smsmith    bcache_data = malloc(bcache_nblks * bcache_blksize);
6140834Smsmith    bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl));
6240834Smsmith    bcache_miss = bit_alloc((bcache_nblks + 1) / 2);
6340834Smsmith    if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) {
6440834Smsmith	if (bcache_miss)
6540834Smsmith	    free(bcache_miss);
6640834Smsmith	if (bcache_ctl)
6740834Smsmith	    free(bcache_ctl);
6840834Smsmith	if (bcache_data)
6940834Smsmith	    free(bcache_data);
7040834Smsmith	bcache_data = NULL;
7140834Smsmith	return(ENOMEM);
7240834Smsmith    }
7340834Smsmith
7440834Smsmith    /* Invalidate the cache */
7540834Smsmith    for (i = 0; i < bcache_nblks; i++)
7640834Smsmith	bcache_ctl[i].bc_stamp = 0;
7740834Smsmith
7840834Smsmith    return(0);
7940834Smsmith}
8040834Smsmith
8140834Smsmith/*
8240834Smsmith * Handle a transfer request; fill in parts of the request that can
8340834Smsmith * be satisfied by the cache, use the supplied strategy routine to do
8440834Smsmith * device I/O and then use the I/O results to populate the cache.
8540834Smsmith *
8640834Smsmith * Requests larger than 1/2 the cache size will be bypassed and go
8740834Smsmith * directly to the disk.  XXX tune this.
8840834Smsmith */
8940834Smsmithint
9040834Smsmithbcache_strategy(void *devdata, int rw, daddr_t blk, size_t size, void *buf, size_t *rsize)
9140834Smsmith{
9240834Smsmith    struct bcache_devdata	*dd = (struct bcache_devdata *)devdata;
9340834Smsmith    int				nblk, p_size;
9440834Smsmith    daddr_t			p_blk;
9540834Smsmith    caddr_t			p_buf;
9640834Smsmith    int				i, j, result;
9740834Smsmith
9840834Smsmith    bcache_ops++;
9940834Smsmith
10040834Smsmith    /* bypass large requests, or when the cache is inactive */
10140834Smsmith    if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) {
10240834Smsmith	DEBUG("bypass %d from %d", size / bcache_blksize, blk);
10340834Smsmith	bcache_bypasses++;
10440834Smsmith	return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize));
10540834Smsmith    }
10640834Smsmith
10740834Smsmith    nblk = size / bcache_blksize;
10840834Smsmith    result = 0;
10940834Smsmith
11040834Smsmith    /* Satisfy any cache hits up front */
11140834Smsmith    for (i = 0; i < nblk; i++) {
11240834Smsmith	if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) {
11340834Smsmith	    bit_set(bcache_miss, i);	/* cache miss */
11440834Smsmith	    bcache_misses++;
11540834Smsmith	} else {
11640834Smsmith	    bit_clear(bcache_miss, i);	/* cache hit */
11740834Smsmith	    bcache_hits++;
11840834Smsmith	}
11940834Smsmith    }
12040834Smsmith
12140834Smsmith    /* Go back and fill in any misses  XXX optimise */
12240834Smsmith    p_blk = -1;
12340834Smsmith    p_buf = NULL;
12440834Smsmith    p_size = 0;
12540834Smsmith    for (i = 0; i < nblk; i++) {
12640834Smsmith	if (bit_test(bcache_miss, i)) {
12740834Smsmith	    /* miss, add to pending transfer */
12840834Smsmith	    if (p_blk == -1) {
12940834Smsmith		p_blk = blk + i;
13040834Smsmith		p_buf = buf + (bcache_blksize * i);
13140834Smsmith		p_size = 1;
13240834Smsmith	    } else {
13340834Smsmith		p_size++;
13440834Smsmith	    }
13540834Smsmith	} else if (p_blk != -1) {
13640834Smsmith	    /* hit, complete pending transfer */
13740834Smsmith	    result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
13840834Smsmith	    if (result != 0)
13940834Smsmith		goto done;
14040834Smsmith	    for (j = 0; j < p_size; j++)
14140834Smsmith		bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
14240834Smsmith	    p_blk = -1;
14340834Smsmith	}
14440834Smsmith    }
14540834Smsmith    if (p_blk != -1) {
14640834Smsmith	/* pending transfer left */
14740834Smsmith	result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
14840834Smsmith	if (result != 0)
14940834Smsmith	    goto done;
15040834Smsmith	for (j = 0; j < p_size; j++)
15140834Smsmith	    bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
15240834Smsmith    }
15340834Smsmith
15440834Smsmith done:
15540834Smsmith    if ((result == 0) && (rsize != NULL))
15640834Smsmith	*rsize = size;
15740834Smsmith    return(result);
15840834Smsmith}
15940834Smsmith
16040834Smsmith
16140834Smsmith/*
16240834Smsmith * Insert a block into the cache.  Retire the oldest block to do so, if required.
16340834Smsmith */
16440834Smsmithstatic void
16540834Smsmithbcache_insert(caddr_t buf, daddr_t blkno)
16640834Smsmith{
16740834Smsmith    time_t	now;
16840834Smsmith    int		i, cand;
16940834Smsmith
17040834Smsmith    time(&now);
17140834Smsmith
17240834Smsmith    /* find the oldest block */
17340834Smsmith    for (cand = 0, i = 1; i < bcache_nblks; i++) {
17440834Smsmith	if (bcache_ctl[i].bc_blkno == blkno) {
17540834Smsmith	    /* reuse old entry */
17640834Smsmith	    cand = i;
17740834Smsmith	    break;
17840834Smsmith	}
17940834Smsmith	if (bcache_ctl[i].bc_stamp < now)
18040834Smsmith	    cand = i;
18140834Smsmith    }
18240834Smsmith
18340834Smsmith    DEBUG("insert blk %d -> %d @ %d", blkno, cand, now);
18440834Smsmith    bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize);
18540834Smsmith    bcache_ctl[cand].bc_blkno = blkno;
18640834Smsmith    bcache_ctl[cand].bc_stamp = now;
18740834Smsmith}
18840834Smsmith
18940834Smsmith/*
19040834Smsmith * Look for a block in the cache.  Blocks more than BCACHE_TIMEOUT seconds old
19140834Smsmith *  may be stale (removable media) and thus are discarded.  Copy the block out
19240834Smsmith * if successful and return zero, or return nonzero on failure.
19340834Smsmith */
19440834Smsmithstatic int
19540834Smsmithbcache_lookup(caddr_t buf, daddr_t blkno)
19640834Smsmith{
19740834Smsmith    time_t	now;
19840834Smsmith    int		i;
19940834Smsmith
20040834Smsmith    time(&now);
20140834Smsmith
20240834Smsmith    for (i = 0; i < bcache_nblks; i++)
20340834Smsmith	/* cache hit? */
20440834Smsmith	if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) {
20540834Smsmith	    bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize);
20640834Smsmith	    DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp);
20740834Smsmith	    return(0);
20840834Smsmith	}
20940834Smsmith    return(ENOENT);
21040834Smsmith}
21140834Smsmith
21240834SmsmithCOMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache);
21340834Smsmith
21440834Smsmithstatic int
21540834Smsmithcommand_bcache(int argc, char *argv[])
21640834Smsmith{
21740834Smsmith    int		i;
21840834Smsmith
21940834Smsmith    for (i = 0; i < bcache_nblks; i++) {
22040834Smsmith	printf("  %02x: %08x %04x", i, bcache_ctl[i].bc_blkno, bcache_ctl[i].bc_stamp & 0xffff);
22140834Smsmith	if (((i + 1) % 4) == 0)
22240834Smsmith	    printf("\n");
22340834Smsmith    }
22440834Smsmith    printf("\n%d ops  %d bypasses  %d hits  %d misses\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses);
22540834Smsmith    return(CMD_OK);
22640834Smsmith}
22740834Smsmith
228