bcache.c revision 41254
140875Smsmith/*- 240875Smsmith * Copyright (c) 1998 Michael Smith <msmith@freebsd.org> 340875Smsmith * All rights reserved. 440875Smsmith * 540875Smsmith * Redistribution and use in source and binary forms, with or without 640875Smsmith * modification, are permitted provided that the following conditions 740875Smsmith * are met: 840875Smsmith * 1. Redistributions of source code must retain the above copyright 940875Smsmith * notice, this list of conditions and the following disclaimer. 1040875Smsmith * 2. Redistributions in binary form must reproduce the above copyright 1140875Smsmith * notice, this list of conditions and the following disclaimer in the 1240875Smsmith * documentation and/or other materials provided with the distribution. 1340875Smsmith * 1440875Smsmith * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1540875Smsmith * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1640875Smsmith * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1740875Smsmith * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1840875Smsmith * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1940875Smsmith * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2040875Smsmith * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2140875Smsmith * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2240875Smsmith * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2340875Smsmith * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2440875Smsmith * SUCH DAMAGE. 2540875Smsmith * 2641254Spaul * $Id: bcache.c,v 1.3 1998/11/04 00:29:01 msmith Exp $ 2740834Smsmith */ 2840834Smsmith 2940834Smsmith/* 3040834Smsmith * Simple LRU block cache 3140834Smsmith */ 3240834Smsmith 3340834Smsmith#include <stand.h> 3440834Smsmith#include <string.h> 3540834Smsmith#include <bitstring.h> 3640834Smsmith 3740834Smsmith#include "bootstrap.h" 3840834Smsmith 3940834Smsmith/* #define BCACHE_DEBUG */ 4040834Smsmith 4140834Smsmith#ifdef BCACHE_DEBUG 4240834Smsmith#define BCACHE_TIMEOUT 10 4340834Smsmith# define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __FUNCTION__ , ## args) 4440834Smsmith#else 4540834Smsmith#define BCACHE_TIMEOUT 2 4640834Smsmith# define DEBUG(fmt, args...) 4740834Smsmith#endif 4840834Smsmith 4940834Smsmith 5040834Smsmithstruct bcachectl 5140834Smsmith{ 5240834Smsmith daddr_t bc_blkno; 5340834Smsmith time_t bc_stamp; 5440835Smsmith int bc_count; 5540834Smsmith}; 5640834Smsmith 5740834Smsmithstatic struct bcachectl *bcache_ctl; 5840834Smsmithstatic caddr_t bcache_data; 5940834Smsmithstatic bitstr_t *bcache_miss; 6040834Smsmithstatic int bcache_nblks; 6140834Smsmithstatic int bcache_blksize; 6240834Smsmithstatic int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses; 6340835Smsmithstatic int bcache_bcount; 6440834Smsmith 6540834Smsmithstatic void bcache_insert(caddr_t buf, daddr_t blkno); 6640834Smsmithstatic int bcache_lookup(caddr_t buf, daddr_t blkno); 6740834Smsmith 6840834Smsmith/* 6940834Smsmith * Initialise the cache for (nblks) of (bsize). 7040834Smsmith */ 7140834Smsmithint 7240834Smsmithbcache_init(int nblks, size_t bsize) 7340834Smsmith{ 7440834Smsmith int i; 7540834Smsmith 7640834Smsmith /* discard any old contents */ 7740834Smsmith if (bcache_data != NULL) { 7840834Smsmith free(bcache_data); 7940834Smsmith bcache_data = NULL; 8040834Smsmith free(bcache_ctl); 8140834Smsmith } 8240834Smsmith 8340834Smsmith /* Allocate control structures */ 8440834Smsmith bcache_nblks = nblks; 8540834Smsmith bcache_blksize = bsize; 8640834Smsmith bcache_data = malloc(bcache_nblks * bcache_blksize); 8740834Smsmith bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl)); 8840834Smsmith bcache_miss = bit_alloc((bcache_nblks + 1) / 2); 8940834Smsmith if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) { 9040834Smsmith if (bcache_miss) 9140834Smsmith free(bcache_miss); 9240834Smsmith if (bcache_ctl) 9340834Smsmith free(bcache_ctl); 9440834Smsmith if (bcache_data) 9540834Smsmith free(bcache_data); 9640834Smsmith bcache_data = NULL; 9740834Smsmith return(ENOMEM); 9840834Smsmith } 9940834Smsmith 10040834Smsmith /* Invalidate the cache */ 10141254Spaul for (i = 0; i < bcache_nblks; i++) { 10240835Smsmith bcache_ctl[i].bc_count = -1; 10341254Spaul bcache_ctl[i].bc_blkno = -1; 10441254Spaul } 10540834Smsmith 10640834Smsmith return(0); 10740834Smsmith} 10840834Smsmith 10940834Smsmith/* 11040834Smsmith * Handle a transfer request; fill in parts of the request that can 11140834Smsmith * be satisfied by the cache, use the supplied strategy routine to do 11240834Smsmith * device I/O and then use the I/O results to populate the cache. 11340834Smsmith * 11440834Smsmith * Requests larger than 1/2 the cache size will be bypassed and go 11540834Smsmith * directly to the disk. XXX tune this. 11640834Smsmith */ 11740834Smsmithint 11840834Smsmithbcache_strategy(void *devdata, int rw, daddr_t blk, size_t size, void *buf, size_t *rsize) 11940834Smsmith{ 12040834Smsmith struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 12140834Smsmith int nblk, p_size; 12240834Smsmith daddr_t p_blk; 12340834Smsmith caddr_t p_buf; 12440834Smsmith int i, j, result; 12540834Smsmith 12640834Smsmith bcache_ops++; 12740834Smsmith 12840834Smsmith /* bypass large requests, or when the cache is inactive */ 12940834Smsmith if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) { 13040834Smsmith DEBUG("bypass %d from %d", size / bcache_blksize, blk); 13140834Smsmith bcache_bypasses++; 13240834Smsmith return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize)); 13340834Smsmith } 13440834Smsmith 13540834Smsmith nblk = size / bcache_blksize; 13640834Smsmith result = 0; 13740834Smsmith 13840834Smsmith /* Satisfy any cache hits up front */ 13940834Smsmith for (i = 0; i < nblk; i++) { 14040834Smsmith if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) { 14140834Smsmith bit_set(bcache_miss, i); /* cache miss */ 14240834Smsmith bcache_misses++; 14340834Smsmith } else { 14440834Smsmith bit_clear(bcache_miss, i); /* cache hit */ 14540834Smsmith bcache_hits++; 14640834Smsmith } 14740834Smsmith } 14840834Smsmith 14940834Smsmith /* Go back and fill in any misses XXX optimise */ 15040834Smsmith p_blk = -1; 15140834Smsmith p_buf = NULL; 15240834Smsmith p_size = 0; 15340834Smsmith for (i = 0; i < nblk; i++) { 15440834Smsmith if (bit_test(bcache_miss, i)) { 15540834Smsmith /* miss, add to pending transfer */ 15640834Smsmith if (p_blk == -1) { 15740834Smsmith p_blk = blk + i; 15840834Smsmith p_buf = buf + (bcache_blksize * i); 15940834Smsmith p_size = 1; 16040834Smsmith } else { 16140834Smsmith p_size++; 16240834Smsmith } 16340834Smsmith } else if (p_blk != -1) { 16440834Smsmith /* hit, complete pending transfer */ 16540834Smsmith result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 16640834Smsmith if (result != 0) 16740834Smsmith goto done; 16840834Smsmith for (j = 0; j < p_size; j++) 16940834Smsmith bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 17040834Smsmith p_blk = -1; 17140834Smsmith } 17240834Smsmith } 17340834Smsmith if (p_blk != -1) { 17440834Smsmith /* pending transfer left */ 17540834Smsmith result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 17640834Smsmith if (result != 0) 17740834Smsmith goto done; 17840834Smsmith for (j = 0; j < p_size; j++) 17940834Smsmith bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 18040834Smsmith } 18140834Smsmith 18240834Smsmith done: 18340834Smsmith if ((result == 0) && (rsize != NULL)) 18440834Smsmith *rsize = size; 18540834Smsmith return(result); 18640834Smsmith} 18740834Smsmith 18840834Smsmith 18940834Smsmith/* 19040834Smsmith * Insert a block into the cache. Retire the oldest block to do so, if required. 19140835Smsmith * 19240835Smsmith * XXX the LRU algorithm will fail after 2^31 blocks have been transferred. 19340834Smsmith */ 19440834Smsmithstatic void 19540834Smsmithbcache_insert(caddr_t buf, daddr_t blkno) 19640834Smsmith{ 19740834Smsmith time_t now; 19840835Smsmith int i, cand, ocount; 19940834Smsmith 20040834Smsmith time(&now); 20140835Smsmith cand = 0; /* assume the first block */ 20240835Smsmith ocount = bcache_ctl[0].bc_count; 20340834Smsmith 20440834Smsmith /* find the oldest block */ 20540835Smsmith for (i = 1; i < bcache_nblks; i++) { 20640834Smsmith if (bcache_ctl[i].bc_blkno == blkno) { 20740834Smsmith /* reuse old entry */ 20840834Smsmith cand = i; 20940834Smsmith break; 21040834Smsmith } 21140835Smsmith if (bcache_ctl[i].bc_count < ocount) { 21240835Smsmith ocount = bcache_ctl[i].bc_count; 21340834Smsmith cand = i; 21440835Smsmith } 21540834Smsmith } 21640834Smsmith 21740835Smsmith DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount); 21840834Smsmith bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize); 21940834Smsmith bcache_ctl[cand].bc_blkno = blkno; 22040834Smsmith bcache_ctl[cand].bc_stamp = now; 22140835Smsmith bcache_ctl[cand].bc_count = bcache_bcount++; 22240834Smsmith} 22340834Smsmith 22440834Smsmith/* 22540834Smsmith * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old 22640835Smsmith * may be stale (removable media) and thus are discarded. Copy the block out 22740834Smsmith * if successful and return zero, or return nonzero on failure. 22840834Smsmith */ 22940834Smsmithstatic int 23040834Smsmithbcache_lookup(caddr_t buf, daddr_t blkno) 23140834Smsmith{ 23240834Smsmith time_t now; 23340834Smsmith int i; 23440834Smsmith 23540834Smsmith time(&now); 23640834Smsmith 23740834Smsmith for (i = 0; i < bcache_nblks; i++) 23840834Smsmith /* cache hit? */ 23940834Smsmith if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) { 24040834Smsmith bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize); 24140834Smsmith DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp); 24240834Smsmith return(0); 24340834Smsmith } 24440834Smsmith return(ENOENT); 24540834Smsmith} 24640834Smsmith 24740834SmsmithCOMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache); 24840834Smsmith 24940834Smsmithstatic int 25040834Smsmithcommand_bcache(int argc, char *argv[]) 25140834Smsmith{ 25240834Smsmith int i; 25340834Smsmith 25440834Smsmith for (i = 0; i < bcache_nblks; i++) { 25540835Smsmith printf("%08x %04x %04x|", bcache_ctl[i].bc_blkno, bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff); 25640834Smsmith if (((i + 1) % 4) == 0) 25740834Smsmith printf("\n"); 25840834Smsmith } 25940834Smsmith printf("\n%d ops %d bypasses %d hits %d misses\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses); 26040834Smsmith return(CMD_OK); 26140834Smsmith} 26240834Smsmith 263