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