bcache.c revision 40834
1272343Sngie/* 2272343Sngie * mjs copyright 3272343Sngie */ 4272343Sngie 5272343Sngie/* 6272343Sngie * Simple LRU block cache 7272343Sngie */ 8272343Sngie 9272343Sngie#include <stand.h> 10272343Sngie#include <string.h> 11272343Sngie#include <bitstring.h> 12272343Sngie 13272343Sngie#include "bootstrap.h" 14272343Sngie 15272343Sngie/* #define BCACHE_DEBUG */ 16272343Sngie 17272343Sngie#ifdef BCACHE_DEBUG 18272343Sngie#define BCACHE_TIMEOUT 10 19272343Sngie# define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __FUNCTION__ , ## args) 20272343Sngie#else 21272343Sngie#define BCACHE_TIMEOUT 2 22272343Sngie# define DEBUG(fmt, args...) 23272343Sngie#endif 24272343Sngie 25272343Sngie 26272343Sngiestruct bcachectl 27272343Sngie{ 28272343Sngie daddr_t bc_blkno; 29272343Sngie time_t bc_stamp; 30272343Sngie}; 31272343Sngie 32272343Sngiestatic struct bcachectl *bcache_ctl; 33272343Sngiestatic caddr_t bcache_data; 34272343Sngiestatic bitstr_t *bcache_miss; 35272343Sngiestatic int bcache_nblks; 36272343Sngiestatic int bcache_blksize; 37272343Sngiestatic int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses; 38272343Sngie 39272343Sngiestatic void bcache_insert(caddr_t buf, daddr_t blkno); 40272343Sngiestatic int bcache_lookup(caddr_t buf, daddr_t blkno); 41272343Sngie 42272343Sngie/* 43272343Sngie * Initialise the cache for (nblks) of (bsize). 44272343Sngie */ 45272343Sngieint 46272343Sngiebcache_init(int nblks, size_t bsize) 47272343Sngie{ 48272343Sngie int i; 49272343Sngie 50272343Sngie /* discard any old contents */ 51272343Sngie if (bcache_data != NULL) { 52272343Sngie free(bcache_data); 53272343Sngie bcache_data = NULL; 54272343Sngie free(bcache_ctl); 55272343Sngie } 56272343Sngie 57272343Sngie /* Allocate control structures */ 58272343Sngie bcache_nblks = nblks; 59272343Sngie bcache_blksize = bsize; 60272343Sngie bcache_data = malloc(bcache_nblks * bcache_blksize); 61272343Sngie bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl)); 62272343Sngie bcache_miss = bit_alloc((bcache_nblks + 1) / 2); 63272343Sngie if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) { 64272343Sngie if (bcache_miss) 65272343Sngie free(bcache_miss); 66272343Sngie if (bcache_ctl) 67272343Sngie free(bcache_ctl); 68272343Sngie if (bcache_data) 69272343Sngie free(bcache_data); 70272343Sngie bcache_data = NULL; 71272343Sngie return(ENOMEM); 72272343Sngie } 73272343Sngie 74272343Sngie /* Invalidate the cache */ 75272343Sngie for (i = 0; i < bcache_nblks; i++) 76272343Sngie bcache_ctl[i].bc_stamp = 0; 77272343Sngie 78272343Sngie return(0); 79272343Sngie} 80272343Sngie 81272343Sngie/* 82272343Sngie * Handle a transfer request; fill in parts of the request that can 83272343Sngie * be satisfied by the cache, use the supplied strategy routine to do 84272343Sngie * device I/O and then use the I/O results to populate the cache. 85272343Sngie * 86272343Sngie * Requests larger than 1/2 the cache size will be bypassed and go 87272343Sngie * directly to the disk. XXX tune this. 88272343Sngie */ 89272343Sngieint 90272343Sngiebcache_strategy(void *devdata, int rw, daddr_t blk, size_t size, void *buf, size_t *rsize) 91272343Sngie{ 92272343Sngie struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 93272343Sngie int nblk, p_size; 94272343Sngie daddr_t p_blk; 95272343Sngie caddr_t p_buf; 96272343Sngie int i, j, result; 97272343Sngie 98272343Sngie bcache_ops++; 99272343Sngie 100272343Sngie /* bypass large requests, or when the cache is inactive */ 101272343Sngie if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) { 102272343Sngie DEBUG("bypass %d from %d", size / bcache_blksize, blk); 103272343Sngie bcache_bypasses++; 104272343Sngie return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize)); 105272343Sngie } 106272343Sngie 107272343Sngie nblk = size / bcache_blksize; 108272343Sngie result = 0; 109272343Sngie 110272343Sngie /* Satisfy any cache hits up front */ 111272343Sngie for (i = 0; i < nblk; i++) { 112272343Sngie if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) { 113272343Sngie bit_set(bcache_miss, i); /* cache miss */ 114272343Sngie bcache_misses++; 115272343Sngie } else { 116272343Sngie bit_clear(bcache_miss, i); /* cache hit */ 117272343Sngie bcache_hits++; 118272343Sngie } 119272343Sngie } 120272343Sngie 121272343Sngie /* Go back and fill in any misses XXX optimise */ 122272343Sngie p_blk = -1; 123272343Sngie p_buf = NULL; 124272343Sngie p_size = 0; 125272343Sngie for (i = 0; i < nblk; i++) { 126272343Sngie if (bit_test(bcache_miss, i)) { 127272343Sngie /* miss, add to pending transfer */ 128272343Sngie if (p_blk == -1) { 129272343Sngie p_blk = blk + i; 130272343Sngie p_buf = buf + (bcache_blksize * i); 131272343Sngie p_size = 1; 132272343Sngie } else { 133272343Sngie p_size++; 134272343Sngie } 135272343Sngie } else if (p_blk != -1) { 136272343Sngie /* hit, complete pending transfer */ 137272343Sngie result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 138272343Sngie if (result != 0) 139272343Sngie goto done; 140272343Sngie for (j = 0; j < p_size; j++) 141272343Sngie bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 142272343Sngie p_blk = -1; 143272343Sngie } 144272343Sngie } 145272343Sngie if (p_blk != -1) { 146272343Sngie /* pending transfer left */ 147272343Sngie result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 148272343Sngie if (result != 0) 149272343Sngie goto done; 150272343Sngie for (j = 0; j < p_size; j++) 151272343Sngie bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 152272343Sngie } 153272343Sngie 154272343Sngie done: 155272343Sngie if ((result == 0) && (rsize != NULL)) 156272343Sngie *rsize = size; 157272343Sngie return(result); 158272343Sngie} 159272343Sngie 160272343Sngie 161272343Sngie/* 162272343Sngie * Insert a block into the cache. Retire the oldest block to do so, if required. 163272343Sngie */ 164272343Sngiestatic void 165272343Sngiebcache_insert(caddr_t buf, daddr_t blkno) 166272343Sngie{ 167272343Sngie time_t now; 168272343Sngie int i, cand; 169272343Sngie 170272343Sngie time(&now); 171272343Sngie 172272343Sngie /* find the oldest block */ 173272343Sngie for (cand = 0, i = 1; i < bcache_nblks; i++) { 174272343Sngie if (bcache_ctl[i].bc_blkno == blkno) { 175272343Sngie /* reuse old entry */ 176272343Sngie cand = i; 177272343Sngie break; 178272343Sngie } 179272343Sngie if (bcache_ctl[i].bc_stamp < now) 180272343Sngie cand = i; 181272343Sngie } 182272343Sngie 183272343Sngie DEBUG("insert blk %d -> %d @ %d", blkno, cand, now); 184272343Sngie bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize); 185272343Sngie bcache_ctl[cand].bc_blkno = blkno; 186272343Sngie bcache_ctl[cand].bc_stamp = now; 187272343Sngie} 188272343Sngie 189272343Sngie/* 190272343Sngie * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old 191 * may be stale (removable media) and thus are discarded. Copy the block out 192 * if successful and return zero, or return nonzero on failure. 193 */ 194static int 195bcache_lookup(caddr_t buf, daddr_t blkno) 196{ 197 time_t now; 198 int i; 199 200 time(&now); 201 202 for (i = 0; i < bcache_nblks; i++) 203 /* cache hit? */ 204 if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) { 205 bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize); 206 DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp); 207 return(0); 208 } 209 return(ENOENT); 210} 211 212COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache); 213 214static int 215command_bcache(int argc, char *argv[]) 216{ 217 int i; 218 219 for (i = 0; i < bcache_nblks; i++) { 220 printf(" %02x: %08x %04x", i, bcache_ctl[i].bc_blkno, bcache_ctl[i].bc_stamp & 0xffff); 221 if (((i + 1) % 4) == 0) 222 printf("\n"); 223 } 224 printf("\n%d ops %d bypasses %d hits %d misses\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses); 225 return(CMD_OK); 226} 227 228