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