bcache.c revision 58080
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: head/sys/boot/common/bcache.c 58080 2000-03-15 01:56:12Z dcs $ 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" , __FUNCTION__ , ## args) 44#else 45#define BCACHE_TIMEOUT 2 46# define DEBUG(fmt, args...) 47#endif 48 49 50struct bcachectl 51{ 52 daddr_t bc_blkno; 53 time_t bc_stamp; 54 int bc_count; 55}; 56 57static struct bcachectl *bcache_ctl; 58static caddr_t bcache_data; 59static bitstr_t *bcache_miss; 60static int bcache_nblks; 61static int bcache_blksize; 62static int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses; 63static int bcache_flushes; 64static int bcache_bcount; 65 66static void bcache_insert(caddr_t buf, daddr_t blkno); 67static int bcache_lookup(caddr_t buf, daddr_t blkno); 68 69/* 70 * Initialise the cache for (nblks) of (bsize). 71 */ 72int 73bcache_init(int nblks, size_t bsize) 74{ 75 /* discard any old contents */ 76 if (bcache_data != NULL) { 77 free(bcache_data); 78 bcache_data = NULL; 79 free(bcache_ctl); 80 } 81 82 /* Allocate control structures */ 83 bcache_nblks = nblks; 84 bcache_blksize = bsize; 85 bcache_data = malloc(bcache_nblks * bcache_blksize); 86 bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl)); 87 bcache_miss = bit_alloc((bcache_nblks + 1) / 2); 88 if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) { 89 if (bcache_miss) 90 free(bcache_miss); 91 if (bcache_ctl) 92 free(bcache_ctl); 93 if (bcache_data) 94 free(bcache_data); 95 bcache_data = NULL; 96 return(ENOMEM); 97 } 98 99 return(0); 100} 101 102/* 103 * Flush the cache 104 */ 105void 106bcache_flush() 107{ 108 int i; 109 110 bcache_flushes++; 111 112 /* Flush the cache */ 113 for (i = 0; i < bcache_nblks; i++) { 114 bcache_ctl[i].bc_count = -1; 115 bcache_ctl[i].bc_blkno = -1; 116 } 117} 118 119/* 120 * Handle a transfer request; fill in parts of the request that can 121 * be satisfied by the cache, use the supplied strategy routine to do 122 * device I/O and then use the I/O results to populate the cache. 123 * 124 * Requests larger than 1/2 the cache size will be bypassed and go 125 * directly to the disk. XXX tune this. 126 */ 127int 128bcache_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, void *buf, size_t *rsize) 129{ 130 static int bcache_unit = -1; 131 struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 132 int nblk, p_size; 133 daddr_t p_blk; 134 caddr_t p_buf; 135 int i, j, result; 136 137 bcache_ops++; 138 139 if(bcache_unit != unit) { 140 bcache_flush(); 141 bcache_unit = unit; 142 } 143 144 /* bypass large requests, or when the cache is inactive */ 145 if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) { 146 DEBUG("bypass %d from %d", size / bcache_blksize, blk); 147 bcache_bypasses++; 148 return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize)); 149 } 150 151 nblk = size / bcache_blksize; 152 result = 0; 153 154 /* Satisfy any cache hits up front */ 155 for (i = 0; i < nblk; i++) { 156 if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) { 157 bit_set(bcache_miss, i); /* cache miss */ 158 bcache_misses++; 159 } else { 160 bit_clear(bcache_miss, i); /* cache hit */ 161 bcache_hits++; 162 } 163 } 164 165 /* Go back and fill in any misses XXX optimise */ 166 p_blk = -1; 167 p_buf = NULL; 168 p_size = 0; 169 for (i = 0; i < nblk; i++) { 170 if (bit_test(bcache_miss, i)) { 171 /* miss, add to pending transfer */ 172 if (p_blk == -1) { 173 p_blk = blk + i; 174 p_buf = buf + (bcache_blksize * i); 175 p_size = 1; 176 } else { 177 p_size++; 178 } 179 } else if (p_blk != -1) { 180 /* hit, complete pending transfer */ 181 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 182 if (result != 0) 183 goto done; 184 for (j = 0; j < p_size; j++) 185 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 186 p_blk = -1; 187 } 188 } 189 if (p_blk != -1) { 190 /* pending transfer left */ 191 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 192 if (result != 0) 193 goto done; 194 for (j = 0; j < p_size; j++) 195 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 196 } 197 198 done: 199 if ((result == 0) && (rsize != NULL)) 200 *rsize = size; 201 return(result); 202} 203 204 205/* 206 * Insert a block into the cache. Retire the oldest block to do so, if required. 207 * 208 * XXX the LRU algorithm will fail after 2^31 blocks have been transferred. 209 */ 210static void 211bcache_insert(caddr_t buf, daddr_t blkno) 212{ 213 time_t now; 214 int i, cand, ocount; 215 216 time(&now); 217 cand = 0; /* assume the first block */ 218 ocount = bcache_ctl[0].bc_count; 219 220 /* find the oldest block */ 221 for (i = 1; i < bcache_nblks; i++) { 222 if (bcache_ctl[i].bc_blkno == blkno) { 223 /* reuse old entry */ 224 cand = i; 225 break; 226 } 227 if (bcache_ctl[i].bc_count < ocount) { 228 ocount = bcache_ctl[i].bc_count; 229 cand = i; 230 } 231 } 232 233 DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount); 234 bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize); 235 bcache_ctl[cand].bc_blkno = blkno; 236 bcache_ctl[cand].bc_stamp = now; 237 bcache_ctl[cand].bc_count = bcache_bcount++; 238} 239 240/* 241 * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old 242 * may be stale (removable media) and thus are discarded. Copy the block out 243 * if successful and return zero, or return nonzero on failure. 244 */ 245static int 246bcache_lookup(caddr_t buf, daddr_t blkno) 247{ 248 time_t now; 249 int i; 250 251 time(&now); 252 253 for (i = 0; i < bcache_nblks; i++) 254 /* cache hit? */ 255 if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) { 256 bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize); 257 DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp); 258 return(0); 259 } 260 return(ENOENT); 261} 262 263COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache); 264 265static int 266command_bcache(int argc, char *argv[]) 267{ 268 int i; 269 270 for (i = 0; i < bcache_nblks; i++) { 271 printf("%08x %04x %04x|", bcache_ctl[i].bc_blkno, (unsigned int)bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff); 272 if (((i + 1) % 4) == 0) 273 printf("\n"); 274 } 275 printf("\n%d ops %d bypasses %d hits %d misses %d flushes\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses, bcache_flushes); 276 return(CMD_OK); 277} 278 279