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 * $FreeBSD: src/sys/boot/common/bcache.c,v 1.12 2003/08/25 23:30:41 obrien Exp $ 27 */ 28 29 /* 30 * Simple LRU block cache 31 */ 32 33 #include <stand.h> 34 #include <string.h> 35 #include <bitstring.h> 36 37 #include "bootstrap.h" 38 39 /* #define BCACHE_DEBUG */ 40 41 #ifdef BCACHE_DEBUG 42 #define BCACHE_TIMEOUT 10 43 # define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __func__ , ## args) 44 #else 45 #define BCACHE_TIMEOUT 2 46 # define DEBUG(fmt, args...) 47 #endif 48 49 50 struct bcachectl 51 { 52 daddr_t bc_blkno; 53 time_t bc_stamp; 54 int bc_count; 55 }; 56 57 static struct bcachectl *bcache_ctl; 58 static caddr_t bcache_data; 59 static bitstr_t *bcache_miss; 60 static u_int bcache_nblks; 61 static u_int bcache_blksize; 62 static u_int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses; 63 static u_int bcache_flushes; 64 static u_int bcache_bcount; 65 66 static void bcache_invalidate(daddr_t blkno); 67 static void bcache_insert(caddr_t buf, daddr_t blkno); 68 static int bcache_lookup(caddr_t buf, daddr_t blkno); 69 70 /* 71 * Initialise the cache for (nblks) of (bsize). 72 */ 73 int 74 bcache_init(u_int nblks, size_t bsize) 75 { 76 /* discard any old contents */ 77 if (bcache_data != NULL) { 78 free(bcache_data); 79 bcache_data = NULL; 80 free(bcache_ctl); 81 } 82 83 /* Allocate control structures */ 84 bcache_nblks = nblks; 85 bcache_blksize = bsize; 86 bcache_data = malloc(bcache_nblks * bcache_blksize); 87 bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl)); 88 bcache_miss = bit_alloc((bcache_nblks + 1) / 2); 89 if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) { 90 if (bcache_miss) 91 free(bcache_miss); 92 if (bcache_ctl) 93 free(bcache_ctl); 94 if (bcache_data) 95 free(bcache_data); 96 bcache_data = NULL; 97 return(ENOMEM); 98 } 99 100 return(0); 101 } 102 103 /* 104 * Flush the cache 105 */ 106 void 107 bcache_flush(void) 108 { 109 u_int i; 110 111 bcache_flushes++; 112 113 /* Flush the cache */ 114 for (i = 0; i < bcache_nblks; i++) { 115 bcache_ctl[i].bc_count = -1; 116 bcache_ctl[i].bc_blkno = -1; 117 } 118 } 119 120 /* 121 * Handle a write request; write directly to the disk, and populate the 122 * cache with the new values. 123 */ 124 static int 125 write_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 126 char *buf, size_t *rsize) 127 { 128 struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 129 daddr_t i, nblk; 130 int err; 131 132 nblk = size / bcache_blksize; 133 134 /* Invalidate the blocks being written */ 135 for (i = 0; i < nblk; i++) { 136 bcache_invalidate(blk + i); 137 } 138 139 /* Write the blocks */ 140 err = dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize); 141 142 /* Populate the block cache with the new data */ 143 if (err == 0) { 144 for (i = 0; i < nblk; i++) { 145 bcache_insert(buf + (i * bcache_blksize),blk + i); 146 } 147 } 148 149 return err; 150 } 151 152 /* 153 * Handle a read request; fill in parts of the request that can 154 * be satisfied by the cache, use the supplied strategy routine to do 155 * device I/O and then use the I/O results to populate the cache. 156 */ 157 static int 158 read_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 159 char *buf, size_t *rsize) 160 { 161 struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 162 int p_size, result; 163 daddr_t p_blk, i, j, nblk; 164 caddr_t p_buf; 165 166 nblk = size / bcache_blksize; 167 result = 0; 168 169 /* Satisfy any cache hits up front */ 170 for (i = 0; i < nblk; i++) { 171 if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) { 172 bit_set(bcache_miss, i); /* cache miss */ 173 bcache_misses++; 174 } else { 175 bit_clear(bcache_miss, i); /* cache hit */ 176 bcache_hits++; 177 } 178 } 179 180 /* Go back and fill in any misses XXX optimise */ 181 p_blk = -1; 182 p_buf = NULL; 183 p_size = 0; 184 for (i = 0; i < nblk; i++) { 185 if (bit_test(bcache_miss, i)) { 186 /* miss, add to pending transfer */ 187 if (p_blk == -1) { 188 p_blk = blk + i; 189 p_buf = buf + (bcache_blksize * i); 190 p_size = 1; 191 } else { 192 p_size++; 193 } 194 } else if (p_blk != -1) { 195 /* hit, complete pending transfer */ 196 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 197 if (result != 0) 198 goto done; 199 for (j = 0; j < p_size; j++) 200 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 201 p_blk = -1; 202 } 203 } 204 if (p_blk != -1) { 205 /* pending transfer left */ 206 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 207 if (result != 0) 208 goto done; 209 for (j = 0; j < p_size; j++) 210 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 211 } 212 213 done: 214 if ((result == 0) && (rsize != NULL)) 215 *rsize = size; 216 return(result); 217 } 218 219 /* 220 * Requests larger than 1/2 the cache size will be bypassed and go 221 * directly to the disk. XXX tune this. 222 */ 223 int 224 bcache_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 225 char *buf, size_t *rsize) 226 { 227 static int bcache_unit = -1; 228 struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 229 230 bcache_ops++; 231 232 if(bcache_unit != unit) { 233 bcache_flush(); 234 bcache_unit = unit; 235 } 236 237 /* bypass large requests, or when the cache is inactive */ 238 if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) { 239 DEBUG("bypass %d from %d", size / bcache_blksize, blk); 240 bcache_bypasses++; 241 return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize)); 242 } 243 244 switch (rw) { 245 case F_READ: 246 return read_strategy(devdata, unit, rw, blk, size, buf, rsize); 247 case F_WRITE: 248 return write_strategy(devdata, unit, rw, blk, size, buf, rsize); 249 } 250 return -1; 251 } 252 253 254 /* 255 * Insert a block into the cache. Retire the oldest block to do so, if required. 256 * 257 * XXX the LRU algorithm will fail after 2^31 blocks have been transferred. 258 */ 259 static void 260 bcache_insert(caddr_t buf, daddr_t blkno) 261 { 262 time_t now; 263 int cand, ocount; 264 u_int i; 265 266 time(&now); 267 cand = 0; /* assume the first block */ 268 ocount = bcache_ctl[0].bc_count; 269 270 /* find the oldest block */ 271 for (i = 1; i < bcache_nblks; i++) { 272 if (bcache_ctl[i].bc_blkno == blkno) { 273 /* reuse old entry */ 274 cand = i; 275 break; 276 } 277 if (bcache_ctl[i].bc_count < ocount) { 278 ocount = bcache_ctl[i].bc_count; 279 cand = i; 280 } 281 } 282 283 DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount); 284 bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize); 285 bcache_ctl[cand].bc_blkno = blkno; 286 bcache_ctl[cand].bc_stamp = now; 287 bcache_ctl[cand].bc_count = bcache_bcount++; 288 } 289 290 /* 291 * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old 292 * may be stale (removable media) and thus are discarded. Copy the block out 293 * if successful and return zero, or return nonzero on failure. 294 */ 295 static int 296 bcache_lookup(caddr_t buf, daddr_t blkno) 297 { 298 time_t now; 299 u_int i; 300 301 time(&now); 302 303 for (i = 0; i < bcache_nblks; i++) 304 /* cache hit? */ 305 if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) { 306 bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize); 307 DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp); 308 return(0); 309 } 310 return(ENOENT); 311 } 312 313 /* 314 * Invalidate a block from the cache. 315 */ 316 static void 317 bcache_invalidate(daddr_t blkno) 318 { 319 u_int i; 320 321 for (i = 0; i < bcache_nblks; i++) { 322 if (bcache_ctl[i].bc_blkno == blkno) { 323 bcache_ctl[i].bc_count = -1; 324 bcache_ctl[i].bc_blkno = -1; 325 DEBUG("invalidate blk %d", blkno); 326 break; 327 } 328 } 329 } 330 331 COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache); 332 333 static int 334 command_bcache(int argc, char *argv[]) 335 { 336 u_int i; 337 338 for (i = 0; i < bcache_nblks; i++) { 339 printf("%08x %04x %04x|", bcache_ctl[i].bc_blkno, (unsigned int)bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff); 340 if (((i + 1) % 4) == 0) 341 printf("\n"); 342 } 343 printf("\n%u ops %u bypasses %u hits %u misses %u flushes\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses, bcache_flushes); 344 return(CMD_OK); 345 } 346 347