bcache.c revision 136097
1/*- 2 * Copyright (c) 1998 Michael Smith <msmith@freebsd.org> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27#include <sys/cdefs.h> 28__FBSDID("$FreeBSD: head/sys/boot/common/bcache.c 136097 2004-10-03 16:34:01Z stefanf $"); 29 30/* 31 * Simple LRU block cache 32 */ 33 34#include <sys/stdint.h> 35 36#include <stand.h> 37#include <string.h> 38#include <bitstring.h> 39 40#include "bootstrap.h" 41 42/* #define BCACHE_DEBUG */ 43 44#ifdef BCACHE_DEBUG 45#define BCACHE_TIMEOUT 10 46# define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __func__ , ## args) 47#else 48#define BCACHE_TIMEOUT 2 49# define DEBUG(fmt, args...) 50#endif 51 52 53struct bcachectl 54{ 55 daddr_t bc_blkno; 56 time_t bc_stamp; 57 int bc_count; 58}; 59 60static struct bcachectl *bcache_ctl; 61static caddr_t bcache_data; 62static bitstr_t *bcache_miss; 63static u_int bcache_nblks; 64static u_int bcache_blksize; 65static u_int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses; 66static u_int bcache_flushes; 67static u_int bcache_bcount; 68 69static void bcache_invalidate(daddr_t blkno); 70static void bcache_insert(caddr_t buf, daddr_t blkno); 71static int bcache_lookup(caddr_t buf, daddr_t blkno); 72 73/* 74 * Initialise the cache for (nblks) of (bsize). 75 */ 76int 77bcache_init(u_int nblks, size_t bsize) 78{ 79 /* discard any old contents */ 80 if (bcache_data != NULL) { 81 free(bcache_data); 82 bcache_data = NULL; 83 free(bcache_ctl); 84 } 85 86 /* Allocate control structures */ 87 bcache_nblks = nblks; 88 bcache_blksize = bsize; 89 bcache_data = malloc(bcache_nblks * bcache_blksize); 90 bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl)); 91 bcache_miss = bit_alloc((bcache_nblks + 1) / 2); 92 if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) { 93 if (bcache_miss) 94 free(bcache_miss); 95 if (bcache_ctl) 96 free(bcache_ctl); 97 if (bcache_data) 98 free(bcache_data); 99 bcache_data = NULL; 100 return(ENOMEM); 101 } 102 103 return(0); 104} 105 106/* 107 * Flush the cache 108 */ 109void 110bcache_flush(void) 111{ 112 u_int i; 113 114 bcache_flushes++; 115 116 /* Flush the cache */ 117 for (i = 0; i < bcache_nblks; i++) { 118 bcache_ctl[i].bc_count = -1; 119 bcache_ctl[i].bc_blkno = -1; 120 } 121} 122 123/* 124 * Handle a write request; write directly to the disk, and populate the 125 * cache with the new values. 126 */ 127static int 128write_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 129 char *buf, size_t *rsize) 130{ 131 struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 132 daddr_t i, nblk; 133 int err; 134 135 nblk = size / bcache_blksize; 136 137 /* Invalidate the blocks being written */ 138 for (i = 0; i < nblk; i++) { 139 bcache_invalidate(blk + i); 140 } 141 142 /* Write the blocks */ 143 err = dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize); 144 145 /* Populate the block cache with the new data */ 146 if (err == 0) { 147 for (i = 0; i < nblk; i++) { 148 bcache_insert(buf + (i * bcache_blksize),blk + i); 149 } 150 } 151 152 return err; 153} 154 155/* 156 * Handle a read request; fill in parts of the request that can 157 * be satisfied by the cache, use the supplied strategy routine to do 158 * device I/O and then use the I/O results to populate the cache. 159 */ 160static int 161read_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 162 char *buf, size_t *rsize) 163{ 164 struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 165 int p_size, result; 166 daddr_t p_blk, i, j, nblk; 167 caddr_t p_buf; 168 169 nblk = size / bcache_blksize; 170 result = 0; 171 172 /* Satisfy any cache hits up front */ 173 for (i = 0; i < nblk; i++) { 174 if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) { 175 bit_set(bcache_miss, i); /* cache miss */ 176 bcache_misses++; 177 } else { 178 bit_clear(bcache_miss, i); /* cache hit */ 179 bcache_hits++; 180 } 181 } 182 183 /* Go back and fill in any misses XXX optimise */ 184 p_blk = -1; 185 p_buf = NULL; 186 p_size = 0; 187 for (i = 0; i < nblk; i++) { 188 if (bit_test(bcache_miss, i)) { 189 /* miss, add to pending transfer */ 190 if (p_blk == -1) { 191 p_blk = blk + i; 192 p_buf = buf + (bcache_blksize * i); 193 p_size = 1; 194 } else { 195 p_size++; 196 } 197 } else if (p_blk != -1) { 198 /* hit, complete pending transfer */ 199 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 200 if (result != 0) 201 goto done; 202 for (j = 0; j < p_size; j++) 203 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 204 p_blk = -1; 205 } 206 } 207 if (p_blk != -1) { 208 /* pending transfer left */ 209 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 210 if (result != 0) 211 goto done; 212 for (j = 0; j < p_size; j++) 213 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 214 } 215 216 done: 217 if ((result == 0) && (rsize != NULL)) 218 *rsize = size; 219 return(result); 220} 221 222/* 223 * Requests larger than 1/2 the cache size will be bypassed and go 224 * directly to the disk. XXX tune this. 225 */ 226int 227bcache_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 228 char *buf, size_t *rsize) 229{ 230 static int bcache_unit = -1; 231 struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 232 233 bcache_ops++; 234 235 if(bcache_unit != unit) { 236 bcache_flush(); 237 bcache_unit = unit; 238 } 239 240 /* bypass large requests, or when the cache is inactive */ 241 if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) { 242 DEBUG("bypass %d from %d", size / bcache_blksize, blk); 243 bcache_bypasses++; 244 return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize)); 245 } 246 247 switch (rw) { 248 case F_READ: 249 return read_strategy(devdata, unit, rw, blk, size, buf, rsize); 250 case F_WRITE: 251 return write_strategy(devdata, unit, rw, blk, size, buf, rsize); 252 } 253 return -1; 254} 255 256 257/* 258 * Insert a block into the cache. Retire the oldest block to do so, if required. 259 * 260 * XXX the LRU algorithm will fail after 2^31 blocks have been transferred. 261 */ 262static void 263bcache_insert(caddr_t buf, daddr_t blkno) 264{ 265 time_t now; 266 int cand, ocount; 267 u_int i; 268 269 time(&now); 270 cand = 0; /* assume the first block */ 271 ocount = bcache_ctl[0].bc_count; 272 273 /* find the oldest block */ 274 for (i = 1; i < bcache_nblks; i++) { 275 if (bcache_ctl[i].bc_blkno == blkno) { 276 /* reuse old entry */ 277 cand = i; 278 break; 279 } 280 if (bcache_ctl[i].bc_count < ocount) { 281 ocount = bcache_ctl[i].bc_count; 282 cand = i; 283 } 284 } 285 286 DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount); 287 bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize); 288 bcache_ctl[cand].bc_blkno = blkno; 289 bcache_ctl[cand].bc_stamp = now; 290 bcache_ctl[cand].bc_count = bcache_bcount++; 291} 292 293/* 294 * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old 295 * may be stale (removable media) and thus are discarded. Copy the block out 296 * if successful and return zero, or return nonzero on failure. 297 */ 298static int 299bcache_lookup(caddr_t buf, daddr_t blkno) 300{ 301 time_t now; 302 u_int i; 303 304 time(&now); 305 306 for (i = 0; i < bcache_nblks; i++) 307 /* cache hit? */ 308 if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) { 309 bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize); 310 DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp); 311 return(0); 312 } 313 return(ENOENT); 314} 315 316/* 317 * Invalidate a block from the cache. 318 */ 319static void 320bcache_invalidate(daddr_t blkno) 321{ 322 u_int i; 323 324 for (i = 0; i < bcache_nblks; i++) { 325 if (bcache_ctl[i].bc_blkno == blkno) { 326 bcache_ctl[i].bc_count = -1; 327 bcache_ctl[i].bc_blkno = -1; 328 DEBUG("invalidate blk %d", blkno); 329 break; 330 } 331 } 332} 333 334COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache); 335 336static int 337command_bcache(int argc, char *argv[]) 338{ 339 u_int i; 340 341 for (i = 0; i < bcache_nblks; i++) { 342 printf("%08jx %04x %04x|", (uintmax_t)bcache_ctl[i].bc_blkno, (unsigned int)bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff); 343 if (((i + 1) % 4) == 0) 344 printf("\n"); 345 } 346 printf("\n%d ops %d bypasses %d hits %d misses %d flushes\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses, bcache_flushes); 347 return(CMD_OK); 348} 349 350