bcache.c revision 40834
1/* 2 * mjs copyright 3 */ 4 5/* 6 * Simple LRU block cache 7 */ 8 9#include <stand.h> 10#include <string.h> 11#include <bitstring.h> 12 13#include "bootstrap.h" 14 15/* #define BCACHE_DEBUG */ 16 17#ifdef BCACHE_DEBUG 18#define BCACHE_TIMEOUT 10 19# define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __FUNCTION__ , ## args) 20#else 21#define BCACHE_TIMEOUT 2 22# define DEBUG(fmt, args...) 23#endif 24 25 26struct bcachectl 27{ 28 daddr_t bc_blkno; 29 time_t bc_stamp; 30}; 31 32static struct bcachectl *bcache_ctl; 33static caddr_t bcache_data; 34static bitstr_t *bcache_miss; 35static int bcache_nblks; 36static int bcache_blksize; 37static int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses; 38 39static void bcache_insert(caddr_t buf, daddr_t blkno); 40static int bcache_lookup(caddr_t buf, daddr_t blkno); 41 42/* 43 * Initialise the cache for (nblks) of (bsize). 44 */ 45int 46bcache_init(int nblks, size_t bsize) 47{ 48 int i; 49 50 /* discard any old contents */ 51 if (bcache_data != NULL) { 52 free(bcache_data); 53 bcache_data = NULL; 54 free(bcache_ctl); 55 } 56 57 /* Allocate control structures */ 58 bcache_nblks = nblks; 59 bcache_blksize = bsize; 60 bcache_data = malloc(bcache_nblks * bcache_blksize); 61 bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl)); 62 bcache_miss = bit_alloc((bcache_nblks + 1) / 2); 63 if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) { 64 if (bcache_miss) 65 free(bcache_miss); 66 if (bcache_ctl) 67 free(bcache_ctl); 68 if (bcache_data) 69 free(bcache_data); 70 bcache_data = NULL; 71 return(ENOMEM); 72 } 73 74 /* Invalidate the cache */ 75 for (i = 0; i < bcache_nblks; i++) 76 bcache_ctl[i].bc_stamp = 0; 77 78 return(0); 79} 80 81/* 82 * Handle a transfer request; fill in parts of the request that can 83 * be satisfied by the cache, use the supplied strategy routine to do 84 * device I/O and then use the I/O results to populate the cache. 85 * 86 * Requests larger than 1/2 the cache size will be bypassed and go 87 * directly to the disk. XXX tune this. 88 */ 89int 90bcache_strategy(void *devdata, int rw, daddr_t blk, size_t size, void *buf, size_t *rsize) 91{ 92 struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 93 int nblk, p_size; 94 daddr_t p_blk; 95 caddr_t p_buf; 96 int i, j, result; 97 98 bcache_ops++; 99 100 /* bypass large requests, or when the cache is inactive */ 101 if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) { 102 DEBUG("bypass %d from %d", size / bcache_blksize, blk); 103 bcache_bypasses++; 104 return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize)); 105 } 106 107 nblk = size / bcache_blksize; 108 result = 0; 109 110 /* Satisfy any cache hits up front */ 111 for (i = 0; i < nblk; i++) { 112 if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) { 113 bit_set(bcache_miss, i); /* cache miss */ 114 bcache_misses++; 115 } else { 116 bit_clear(bcache_miss, i); /* cache hit */ 117 bcache_hits++; 118 } 119 } 120 121 /* Go back and fill in any misses XXX optimise */ 122 p_blk = -1; 123 p_buf = NULL; 124 p_size = 0; 125 for (i = 0; i < nblk; i++) { 126 if (bit_test(bcache_miss, i)) { 127 /* miss, add to pending transfer */ 128 if (p_blk == -1) { 129 p_blk = blk + i; 130 p_buf = buf + (bcache_blksize * i); 131 p_size = 1; 132 } else { 133 p_size++; 134 } 135 } else if (p_blk != -1) { 136 /* hit, complete pending transfer */ 137 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 138 if (result != 0) 139 goto done; 140 for (j = 0; j < p_size; j++) 141 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 142 p_blk = -1; 143 } 144 } 145 if (p_blk != -1) { 146 /* pending transfer left */ 147 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 148 if (result != 0) 149 goto done; 150 for (j = 0; j < p_size; j++) 151 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 152 } 153 154 done: 155 if ((result == 0) && (rsize != NULL)) 156 *rsize = size; 157 return(result); 158} 159 160 161/* 162 * Insert a block into the cache. Retire the oldest block to do so, if required. 163 */ 164static void 165bcache_insert(caddr_t buf, daddr_t blkno) 166{ 167 time_t now; 168 int i, cand; 169 170 time(&now); 171 172 /* find the oldest block */ 173 for (cand = 0, i = 1; i < bcache_nblks; i++) { 174 if (bcache_ctl[i].bc_blkno == blkno) { 175 /* reuse old entry */ 176 cand = i; 177 break; 178 } 179 if (bcache_ctl[i].bc_stamp < now) 180 cand = i; 181 } 182 183 DEBUG("insert blk %d -> %d @ %d", blkno, cand, now); 184 bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize); 185 bcache_ctl[cand].bc_blkno = blkno; 186 bcache_ctl[cand].bc_stamp = now; 187} 188 189/* 190 * 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