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: releng/10.3/sys/boot/common/bcache.c 136097 2004-10-03 16:34:01Z stefanf $"); 29119483Sobrien 3040834Smsmith/* 3140834Smsmith * Simple LRU block cache 3240834Smsmith */ 3340834Smsmith 34136097Sstefanf#include <sys/stdint.h> 35136097Sstefanf 3640834Smsmith#include <stand.h> 3740834Smsmith#include <string.h> 3840834Smsmith#include <bitstring.h> 3940834Smsmith 4040834Smsmith#include "bootstrap.h" 4140834Smsmith 4240834Smsmith/* #define BCACHE_DEBUG */ 4340834Smsmith 4440834Smsmith#ifdef BCACHE_DEBUG 4540834Smsmith#define BCACHE_TIMEOUT 10 4687599Sobrien# define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __func__ , ## args) 4740834Smsmith#else 4840834Smsmith#define BCACHE_TIMEOUT 2 4940834Smsmith# define DEBUG(fmt, args...) 5040834Smsmith#endif 5140834Smsmith 5240834Smsmith 5340834Smsmithstruct bcachectl 5440834Smsmith{ 5540834Smsmith daddr_t bc_blkno; 5640834Smsmith time_t bc_stamp; 5740835Smsmith int bc_count; 5840834Smsmith}; 5940834Smsmith 6040834Smsmithstatic struct bcachectl *bcache_ctl; 6140834Smsmithstatic caddr_t bcache_data; 6240834Smsmithstatic bitstr_t *bcache_miss; 6364187Sjhbstatic u_int bcache_nblks; 6464187Sjhbstatic u_int bcache_blksize; 6564187Sjhbstatic u_int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses; 6664187Sjhbstatic u_int bcache_flushes; 6764187Sjhbstatic u_int bcache_bcount; 6840834Smsmith 6987634Sjhbstatic void bcache_invalidate(daddr_t blkno); 7040834Smsmithstatic void bcache_insert(caddr_t buf, daddr_t blkno); 7140834Smsmithstatic int bcache_lookup(caddr_t buf, daddr_t blkno); 7240834Smsmith 7340834Smsmith/* 7440834Smsmith * Initialise the cache for (nblks) of (bsize). 7540834Smsmith */ 7640834Smsmithint 7764187Sjhbbcache_init(u_int nblks, size_t bsize) 7840834Smsmith{ 7940834Smsmith /* discard any old contents */ 8040834Smsmith if (bcache_data != NULL) { 8140834Smsmith free(bcache_data); 8240834Smsmith bcache_data = NULL; 8340834Smsmith free(bcache_ctl); 8440834Smsmith } 8540834Smsmith 8640834Smsmith /* Allocate control structures */ 8740834Smsmith bcache_nblks = nblks; 8840834Smsmith bcache_blksize = bsize; 8940834Smsmith bcache_data = malloc(bcache_nblks * bcache_blksize); 9040834Smsmith bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl)); 9140834Smsmith bcache_miss = bit_alloc((bcache_nblks + 1) / 2); 9240834Smsmith if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) { 9340834Smsmith if (bcache_miss) 9440834Smsmith free(bcache_miss); 9540834Smsmith if (bcache_ctl) 9640834Smsmith free(bcache_ctl); 9740834Smsmith if (bcache_data) 9840834Smsmith free(bcache_data); 9940834Smsmith bcache_data = NULL; 10040834Smsmith return(ENOMEM); 10140834Smsmith } 10240834Smsmith 10358080Sdcs return(0); 10458080Sdcs} 10558080Sdcs 10658080Sdcs/* 10758080Sdcs * Flush the cache 10858080Sdcs */ 10958080Sdcsvoid 11064187Sjhbbcache_flush(void) 11158080Sdcs{ 11264187Sjhb u_int i; 11358080Sdcs 11458080Sdcs bcache_flushes++; 11558080Sdcs 11658080Sdcs /* Flush the cache */ 11741254Spaul for (i = 0; i < bcache_nblks; i++) { 11840835Smsmith bcache_ctl[i].bc_count = -1; 11941254Spaul bcache_ctl[i].bc_blkno = -1; 12041254Spaul } 12140834Smsmith} 12240834Smsmith 12387634Sjhb/* 12487634Sjhb * Handle a write request; write directly to the disk, and populate the 12587634Sjhb * cache with the new values. 12687634Sjhb */ 12787634Sjhbstatic int 12887634Sjhbwrite_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 12987634Sjhb char *buf, size_t *rsize) 13087634Sjhb{ 13187634Sjhb struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 13287634Sjhb daddr_t i, nblk; 13387634Sjhb int err; 13487634Sjhb 13587634Sjhb nblk = size / bcache_blksize; 13687634Sjhb 13787634Sjhb /* Invalidate the blocks being written */ 13887634Sjhb for (i = 0; i < nblk; i++) { 13987634Sjhb bcache_invalidate(blk + i); 14087634Sjhb } 14187634Sjhb 14287634Sjhb /* Write the blocks */ 14387634Sjhb err = dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize); 14487634Sjhb 14587634Sjhb /* Populate the block cache with the new data */ 14687634Sjhb if (err == 0) { 14787634Sjhb for (i = 0; i < nblk; i++) { 14887634Sjhb bcache_insert(buf + (i * bcache_blksize),blk + i); 14987634Sjhb } 15087634Sjhb } 15187634Sjhb 15287634Sjhb return err; 15387634Sjhb} 15487634Sjhb 15587634Sjhb/* 15687634Sjhb * Handle a read request; fill in parts of the request that can 15740834Smsmith * be satisfied by the cache, use the supplied strategy routine to do 15840834Smsmith * device I/O and then use the I/O results to populate the cache. 15940834Smsmith */ 16087634Sjhbstatic int 16187634Sjhbread_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 16264187Sjhb char *buf, size_t *rsize) 16340834Smsmith{ 16440834Smsmith struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 16564187Sjhb int p_size, result; 16664187Sjhb daddr_t p_blk, i, j, nblk; 16740834Smsmith caddr_t p_buf; 16840834Smsmith 16940834Smsmith nblk = size / bcache_blksize; 17040834Smsmith result = 0; 17140834Smsmith 17240834Smsmith /* Satisfy any cache hits up front */ 17340834Smsmith for (i = 0; i < nblk; i++) { 17440834Smsmith if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) { 17540834Smsmith bit_set(bcache_miss, i); /* cache miss */ 17640834Smsmith bcache_misses++; 17740834Smsmith } else { 17840834Smsmith bit_clear(bcache_miss, i); /* cache hit */ 17940834Smsmith bcache_hits++; 18040834Smsmith } 18140834Smsmith } 18240834Smsmith 18340834Smsmith /* Go back and fill in any misses XXX optimise */ 18440834Smsmith p_blk = -1; 18540834Smsmith p_buf = NULL; 18640834Smsmith p_size = 0; 18740834Smsmith for (i = 0; i < nblk; i++) { 18840834Smsmith if (bit_test(bcache_miss, i)) { 18940834Smsmith /* miss, add to pending transfer */ 19040834Smsmith if (p_blk == -1) { 19140834Smsmith p_blk = blk + i; 19240834Smsmith p_buf = buf + (bcache_blksize * i); 19340834Smsmith p_size = 1; 19440834Smsmith } else { 19540834Smsmith p_size++; 19640834Smsmith } 19740834Smsmith } else if (p_blk != -1) { 19840834Smsmith /* hit, complete pending transfer */ 19940834Smsmith result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 20040834Smsmith if (result != 0) 20140834Smsmith goto done; 20240834Smsmith for (j = 0; j < p_size; j++) 20340834Smsmith bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 20440834Smsmith p_blk = -1; 20540834Smsmith } 20640834Smsmith } 20740834Smsmith if (p_blk != -1) { 20840834Smsmith /* pending transfer left */ 20940834Smsmith result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL); 21040834Smsmith if (result != 0) 21140834Smsmith goto done; 21240834Smsmith for (j = 0; j < p_size; j++) 21340834Smsmith bcache_insert(p_buf + (j * bcache_blksize), p_blk + j); 21440834Smsmith } 21540834Smsmith 21640834Smsmith done: 21740834Smsmith if ((result == 0) && (rsize != NULL)) 21840834Smsmith *rsize = size; 21940834Smsmith return(result); 22040834Smsmith} 22140834Smsmith 22287634Sjhb/* 22387634Sjhb * Requests larger than 1/2 the cache size will be bypassed and go 22487634Sjhb * directly to the disk. XXX tune this. 22587634Sjhb */ 22687634Sjhbint 22787634Sjhbbcache_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size, 22887634Sjhb char *buf, size_t *rsize) 22987634Sjhb{ 23087634Sjhb static int bcache_unit = -1; 23187634Sjhb struct bcache_devdata *dd = (struct bcache_devdata *)devdata; 23240834Smsmith 23387634Sjhb bcache_ops++; 23487634Sjhb 23587634Sjhb if(bcache_unit != unit) { 23687634Sjhb bcache_flush(); 23787634Sjhb bcache_unit = unit; 23887634Sjhb } 23987634Sjhb 24087634Sjhb /* bypass large requests, or when the cache is inactive */ 24187634Sjhb if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) { 24287634Sjhb DEBUG("bypass %d from %d", size / bcache_blksize, blk); 24387634Sjhb bcache_bypasses++; 24487634Sjhb return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize)); 24587634Sjhb } 24687634Sjhb 24787634Sjhb switch (rw) { 24887634Sjhb case F_READ: 24987634Sjhb return read_strategy(devdata, unit, rw, blk, size, buf, rsize); 25087634Sjhb case F_WRITE: 25187634Sjhb return write_strategy(devdata, unit, rw, blk, size, buf, rsize); 25287634Sjhb } 25387634Sjhb return -1; 25487634Sjhb} 25587634Sjhb 25687634Sjhb 25740834Smsmith/* 25840834Smsmith * Insert a block into the cache. Retire the oldest block to do so, if required. 25940835Smsmith * 26040835Smsmith * XXX the LRU algorithm will fail after 2^31 blocks have been transferred. 26140834Smsmith */ 26240834Smsmithstatic void 26340834Smsmithbcache_insert(caddr_t buf, daddr_t blkno) 26440834Smsmith{ 26540834Smsmith time_t now; 26664187Sjhb int cand, ocount; 26764187Sjhb u_int i; 26840834Smsmith 26940834Smsmith time(&now); 27040835Smsmith cand = 0; /* assume the first block */ 27140835Smsmith ocount = bcache_ctl[0].bc_count; 27240834Smsmith 27340834Smsmith /* find the oldest block */ 27440835Smsmith for (i = 1; i < bcache_nblks; i++) { 27540834Smsmith if (bcache_ctl[i].bc_blkno == blkno) { 27640834Smsmith /* reuse old entry */ 27740834Smsmith cand = i; 27840834Smsmith break; 27940834Smsmith } 28040835Smsmith if (bcache_ctl[i].bc_count < ocount) { 28140835Smsmith ocount = bcache_ctl[i].bc_count; 28240834Smsmith cand = i; 28340835Smsmith } 28440834Smsmith } 28540834Smsmith 28640835Smsmith DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount); 28740834Smsmith bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize); 28840834Smsmith bcache_ctl[cand].bc_blkno = blkno; 28940834Smsmith bcache_ctl[cand].bc_stamp = now; 29040835Smsmith bcache_ctl[cand].bc_count = bcache_bcount++; 29140834Smsmith} 29240834Smsmith 29340834Smsmith/* 29440834Smsmith * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old 29540835Smsmith * may be stale (removable media) and thus are discarded. Copy the block out 29640834Smsmith * if successful and return zero, or return nonzero on failure. 29740834Smsmith */ 29840834Smsmithstatic int 29940834Smsmithbcache_lookup(caddr_t buf, daddr_t blkno) 30040834Smsmith{ 30140834Smsmith time_t now; 30264187Sjhb u_int i; 30340834Smsmith 30440834Smsmith time(&now); 30540834Smsmith 30640834Smsmith for (i = 0; i < bcache_nblks; i++) 30740834Smsmith /* cache hit? */ 30840834Smsmith if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) { 30940834Smsmith bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize); 31040834Smsmith DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp); 31140834Smsmith return(0); 31240834Smsmith } 31340834Smsmith return(ENOENT); 31440834Smsmith} 31540834Smsmith 31687634Sjhb/* 31787634Sjhb * Invalidate a block from the cache. 31887634Sjhb */ 31987634Sjhbstatic void 32087634Sjhbbcache_invalidate(daddr_t blkno) 32187634Sjhb{ 32287634Sjhb u_int i; 32387634Sjhb 32487634Sjhb for (i = 0; i < bcache_nblks; i++) { 32587634Sjhb if (bcache_ctl[i].bc_blkno == blkno) { 32687634Sjhb bcache_ctl[i].bc_count = -1; 32787634Sjhb bcache_ctl[i].bc_blkno = -1; 32887634Sjhb DEBUG("invalidate blk %d", blkno); 32987634Sjhb break; 33087634Sjhb } 33187634Sjhb } 33287634Sjhb} 33387634Sjhb 33440834SmsmithCOMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache); 33540834Smsmith 33640834Smsmithstatic int 33740834Smsmithcommand_bcache(int argc, char *argv[]) 33840834Smsmith{ 33964187Sjhb u_int i; 34040834Smsmith 34140834Smsmith for (i = 0; i < bcache_nblks; i++) { 342136097Sstefanf printf("%08jx %04x %04x|", (uintmax_t)bcache_ctl[i].bc_blkno, (unsigned int)bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff); 34340834Smsmith if (((i + 1) % 4) == 0) 34440834Smsmith printf("\n"); 34540834Smsmith } 34658080Sdcs printf("\n%d ops %d bypasses %d hits %d misses %d flushes\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses, bcache_flushes); 34740834Smsmith return(CMD_OK); 34840834Smsmith} 34940834Smsmith 350