bcache.c revision 119483
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. 2540834Smsmith */ 2640834Smsmith 27119483Sobrien#include <sys/cdefs.h> 28119483Sobrien__FBSDID("$FreeBSD: head/sys/boot/common/bcache.c 119483 2003-08-25 23:30:41Z obrien $"); 29119483Sobrien 3040834Smsmith/* 3140834Smsmith * Simple LRU block cache 3240834Smsmith */ 3340834Smsmith 3440834Smsmith#include <stand.h> 3540834Smsmith#include <string.h> 3640834Smsmith#include <bitstring.h> 3740834Smsmith 3840834Smsmith#include "bootstrap.h" 3940834Smsmith 4040834Smsmith/* #define BCACHE_DEBUG */ 4140834Smsmith 4240834Smsmith#ifdef BCACHE_DEBUG 4340834Smsmith#define BCACHE_TIMEOUT 10 4487599Sobrien# define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __func__ , ## args) 4540834Smsmith#else 4640834Smsmith#define BCACHE_TIMEOUT 2 4740834Smsmith# define DEBUG(fmt, args...) 4840834Smsmith#endif 4940834Smsmith 5040834Smsmith 5140834Smsmithstruct bcachectl 5240834Smsmith{ 5340834Smsmith daddr_t bc_blkno; 5440834Smsmith time_t bc_stamp; 5540835Smsmith int bc_count; 5640834Smsmith}; 5740834Smsmith 5840834Smsmithstatic struct bcachectl *bcache_ctl; 5940834Smsmithstatic caddr_t bcache_data; 6040834Smsmithstatic bitstr_t *bcache_miss; 6164187Sjhbstatic u_int bcache_nblks; 6264187Sjhbstatic u_int bcache_blksize; 6364187Sjhbstatic u_int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses; 6464187Sjhbstatic u_int bcache_flushes; 6564187Sjhbstatic u_int bcache_bcount; 6640834Smsmith 6787634Sjhbstatic void bcache_invalidate(daddr_t blkno); 6840834Smsmithstatic void bcache_insert(caddr_t buf, daddr_t blkno); 6940834Smsmithstatic int bcache_lookup(caddr_t buf, daddr_t blkno); 7040834Smsmith 7140834Smsmith/* 7240834Smsmith * Initialise the cache for (nblks) of (bsize). 7340834Smsmith */ 7440834Smsmithint 7564187Sjhbbcache_init(u_int nblks, size_t bsize) 7640834Smsmith{ 7740834Smsmith /* discard any old contents */ 7840834Smsmith if (bcache_data != NULL) { 7940834Smsmith free(bcache_data); 8040834Smsmith bcache_data = NULL; 8140834Smsmith free(bcache_ctl); 8240834Smsmith } 8340834Smsmith 8440834Smsmith /* Allocate control structures */ 8540834Smsmith bcache_nblks = nblks; 8640834Smsmith bcache_blksize = bsize; 8740834Smsmith bcache_data = malloc(bcache_nblks * bcache_blksize); 8840834Smsmith bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl)); 8940834Smsmith bcache_miss = bit_alloc((bcache_nblks + 1) / 2); 9040834Smsmith if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) { 9140834Smsmith if (bcache_miss) 9240834Smsmith free(bcache_miss); 9340834Smsmith if (bcache_ctl) 9440834Smsmith free(bcache_ctl); 9540834Smsmith if (bcache_data) 9640834Smsmith free(bcache_data); 9740834Smsmith bcache_data = NULL; 9840834Smsmith return(ENOMEM); 9940834Smsmith } 10040834Smsmith 10158080Sdcs return(0); 10258080Sdcs} 10358080Sdcs 10458080Sdcs/* 10558080Sdcs * Flush the cache 10658080Sdcs */ 10758080Sdcsvoid 10864187Sjhbbcache_flush(void) 10958080Sdcs{ 11064187Sjhb u_int i; 11158080Sdcs 11258080Sdcs bcache_flushes++; 11358080Sdcs 11458080Sdcs /* Flush the cache */ 11541254Spaul for (i = 0; i < bcache_nblks; i++) { 11640835Smsmith bcache_ctl[i].bc_count = -1; 11741254Spaul bcache_ctl[i].bc_blkno = -1; 11841254Spaul } 11940834Smsmith} 12040834Smsmith 12187634Sjhb/* 12287634Sjhb * Handle a write request; write directly to the disk, and populate the 12387634Sjhb * cache with the new values. 12487634Sjhb */ 12587634Sjhbstatic int 12687634Sjhbwrite_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 12787634Sjhb char *buf, size_t *rsize) 12887634Sjhb{ 12987634Sjhb struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 13087634Sjhb daddr_t i, nblk; 13187634Sjhb int err; 13287634Sjhb 13387634Sjhb nblk = size / bcache_blksize; 13487634Sjhb 13587634Sjhb /* Invalidate the blocks being written */ 13687634Sjhb for (i = 0; i < nblk; i++) { 13787634Sjhb bcache_invalidate(blk + i); 13887634Sjhb } 13987634Sjhb 14087634Sjhb /* Write the blocks */ 14187634Sjhb err = dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize); 14287634Sjhb 14387634Sjhb /* Populate the block cache with the new data */ 14487634Sjhb if (err == 0) { 14587634Sjhb for (i = 0; i < nblk; i++) { 14687634Sjhb bcache_insert(buf + (i * bcache_blksize),blk + i); 14787634Sjhb } 14887634Sjhb } 14987634Sjhb 15087634Sjhb return err; 15187634Sjhb} 15287634Sjhb 15387634Sjhb/* 15487634Sjhb * Handle a read request; fill in parts of the request that can 15540834Smsmith * be satisfied by the cache, use the supplied strategy routine to do 15640834Smsmith * device I/O and then use the I/O results to populate the cache. 15740834Smsmith */ 15887634Sjhbstatic int 15987634Sjhbread_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 16064187Sjhb char *buf, size_t *rsize) 16140834Smsmith{ 16240834Smsmith struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 16364187Sjhb int p_size, result; 16464187Sjhb daddr_t p_blk, i, j, nblk; 16540834Smsmith caddr_t p_buf; 16640834Smsmith 16740834Smsmith nblk = size / bcache_blksize; 16840834Smsmith result = 0; 16940834Smsmith 17040834Smsmith /* Satisfy any cache hits up front */ 17140834Smsmith for (i = 0; i < nblk; i++) { 17240834Smsmith if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) { 17340834Smsmith bit_set(bcache_miss, i); /* cache miss */ 17440834Smsmith bcache_misses++; 17540834Smsmith } else { 17640834Smsmith bit_clear(bcache_miss, i); /* cache hit */ 17740834Smsmith bcache_hits++; 17840834Smsmith } 17940834Smsmith } 18040834Smsmith 18140834Smsmith /* Go back and fill in any misses XXX optimise */ 18240834Smsmith p_blk = -1; 18340834Smsmith p_buf = NULL; 18440834Smsmith p_size = 0; 18540834Smsmith for (i = 0; i < nblk; i++) { 18640834Smsmith if (bit_test(bcache_miss, i)) { 18740834Smsmith /* miss, add to pending transfer */ 18840834Smsmith if (p_blk == -1) { 18940834Smsmith p_blk = blk + i; 19040834Smsmith p_buf = buf + (bcache_blksize * i); 19140834Smsmith p_size = 1; 19240834Smsmith } else { 19340834Smsmith p_size++; 19440834Smsmith } 19540834Smsmith } else if (p_blk != -1) { 19640834Smsmith /* hit, complete pending transfer */ 19740834Smsmith result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 19840834Smsmith if (result != 0) 19940834Smsmith goto done; 20040834Smsmith for (j = 0; j < p_size; j++) 20140834Smsmith bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 20240834Smsmith p_blk = -1; 20340834Smsmith } 20440834Smsmith } 20540834Smsmith if (p_blk != -1) { 20640834Smsmith /* pending transfer left */ 20740834Smsmith result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 20840834Smsmith if (result != 0) 20940834Smsmith goto done; 21040834Smsmith for (j = 0; j < p_size; j++) 21140834Smsmith bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 21240834Smsmith } 21340834Smsmith 21440834Smsmith done: 21540834Smsmith if ((result == 0) && (rsize != NULL)) 21640834Smsmith *rsize = size; 21740834Smsmith return(result); 21840834Smsmith} 21940834Smsmith 22087634Sjhb/* 22187634Sjhb * Requests larger than 1/2 the cache size will be bypassed and go 22287634Sjhb * directly to the disk. XXX tune this. 22387634Sjhb */ 22487634Sjhbint 22587634Sjhbbcache_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 22687634Sjhb char *buf, size_t *rsize) 22787634Sjhb{ 22887634Sjhb static int bcache_unit = -1; 22987634Sjhb struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 23040834Smsmith 23187634Sjhb bcache_ops++; 23287634Sjhb 23387634Sjhb if(bcache_unit != unit) { 23487634Sjhb bcache_flush(); 23587634Sjhb bcache_unit = unit; 23687634Sjhb } 23787634Sjhb 23887634Sjhb /* bypass large requests, or when the cache is inactive */ 23987634Sjhb if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) { 24087634Sjhb DEBUG("bypass %d from %d", size / bcache_blksize, blk); 24187634Sjhb bcache_bypasses++; 24287634Sjhb return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize)); 24387634Sjhb } 24487634Sjhb 24587634Sjhb switch (rw) { 24687634Sjhb case F_READ: 24787634Sjhb return read_strategy(devdata, unit, rw, blk, size, buf, rsize); 24887634Sjhb case F_WRITE: 24987634Sjhb return write_strategy(devdata, unit, rw, blk, size, buf, rsize); 25087634Sjhb } 25187634Sjhb return -1; 25287634Sjhb} 25387634Sjhb 25487634Sjhb 25540834Smsmith/* 25640834Smsmith * Insert a block into the cache. Retire the oldest block to do so, if required. 25740835Smsmith * 25840835Smsmith * XXX the LRU algorithm will fail after 2^31 blocks have been transferred. 25940834Smsmith */ 26040834Smsmithstatic void 26140834Smsmithbcache_insert(caddr_t buf, daddr_t blkno) 26240834Smsmith{ 26340834Smsmith time_t now; 26464187Sjhb int cand, ocount; 26564187Sjhb u_int i; 26640834Smsmith 26740834Smsmith time(&now); 26840835Smsmith cand = 0; /* assume the first block */ 26940835Smsmith ocount = bcache_ctl[0].bc_count; 27040834Smsmith 27140834Smsmith /* find the oldest block */ 27240835Smsmith for (i = 1; i < bcache_nblks; i++) { 27340834Smsmith if (bcache_ctl[i].bc_blkno == blkno) { 27440834Smsmith /* reuse old entry */ 27540834Smsmith cand = i; 27640834Smsmith break; 27740834Smsmith } 27840835Smsmith if (bcache_ctl[i].bc_count < ocount) { 27940835Smsmith ocount = bcache_ctl[i].bc_count; 28040834Smsmith cand = i; 28140835Smsmith } 28240834Smsmith } 28340834Smsmith 28440835Smsmith DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount); 28540834Smsmith bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize); 28640834Smsmith bcache_ctl[cand].bc_blkno = blkno; 28740834Smsmith bcache_ctl[cand].bc_stamp = now; 28840835Smsmith bcache_ctl[cand].bc_count = bcache_bcount++; 28940834Smsmith} 29040834Smsmith 29140834Smsmith/* 29240834Smsmith * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old 29340835Smsmith * may be stale (removable media) and thus are discarded. Copy the block out 29440834Smsmith * if successful and return zero, or return nonzero on failure. 29540834Smsmith */ 29640834Smsmithstatic int 29740834Smsmithbcache_lookup(caddr_t buf, daddr_t blkno) 29840834Smsmith{ 29940834Smsmith time_t now; 30064187Sjhb u_int i; 30140834Smsmith 30240834Smsmith time(&now); 30340834Smsmith 30440834Smsmith for (i = 0; i < bcache_nblks; i++) 30540834Smsmith /* cache hit? */ 30640834Smsmith if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) { 30740834Smsmith bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize); 30840834Smsmith DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp); 30940834Smsmith return(0); 31040834Smsmith } 31140834Smsmith return(ENOENT); 31240834Smsmith} 31340834Smsmith 31487634Sjhb/* 31587634Sjhb * Invalidate a block from the cache. 31687634Sjhb */ 31787634Sjhbstatic void 31887634Sjhbbcache_invalidate(daddr_t blkno) 31987634Sjhb{ 32087634Sjhb u_int i; 32187634Sjhb 32287634Sjhb for (i = 0; i < bcache_nblks; i++) { 32387634Sjhb if (bcache_ctl[i].bc_blkno == blkno) { 32487634Sjhb bcache_ctl[i].bc_count = -1; 32587634Sjhb bcache_ctl[i].bc_blkno = -1; 32687634Sjhb DEBUG("invalidate blk %d", blkno); 32787634Sjhb break; 32887634Sjhb } 32987634Sjhb } 33087634Sjhb} 33187634Sjhb 33240834SmsmithCOMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache); 33340834Smsmith 33440834Smsmithstatic int 33540834Smsmithcommand_bcache(int argc, char *argv[]) 33640834Smsmith{ 33764187Sjhb u_int i; 33840834Smsmith 33940834Smsmith for (i = 0; i < bcache_nblks; i++) { 34043600Sdcs printf("%08x %04x %04x|", bcache_ctl[i].bc_blkno, (unsigned int)bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff); 34140834Smsmith if (((i + 1) % 4) == 0) 34240834Smsmith printf("\n"); 34340834Smsmith } 34458080Sdcs printf("\n%d ops %d bypasses %d hits %d misses %d flushes\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses, bcache_flushes); 34540834Smsmith return(CMD_OK); 34640834Smsmith} 34740834Smsmith 348