2 * Copyright (c) 1998 Michael Smith <msmith@freebsd.org>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
26 * $FreeBSD: src/sys/boot/common/bcache.c,v 1.6.2.2 2000/12/28 13:12:31 ps Exp $
27 * $DragonFly: src/sys/boot/common/bcache.c,v 1.2 2003/06/17 04:28:16 dillon Exp $
31 * Simple LRU block cache
36 #include <bitstring.h>
38 #include "bootstrap.h"
40 /* #define BCACHE_DEBUG */
43 #define BCACHE_TIMEOUT 10
44 # define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __FUNCTION__ , ## args)
46 #define BCACHE_TIMEOUT 2
47 # define DEBUG(fmt, args...)
58 static struct bcachectl *bcache_ctl;
59 static caddr_t bcache_data;
60 static bitstr_t *bcache_miss;
61 static u_int bcache_nblks;
62 static u_int bcache_blksize;
63 static u_int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses;
64 static u_int bcache_flushes;
65 static u_int bcache_bcount;
67 static void bcache_insert(caddr_t buf, daddr_t blkno);
68 static int bcache_lookup(caddr_t buf, daddr_t blkno);
71 * Initialise the cache for (nblks) of (bsize).
74 bcache_init(u_int nblks, size_t bsize)
76 /* discard any old contents */
77 if (bcache_data != NULL) {
83 /* Allocate control structures */
85 bcache_blksize = bsize;
86 bcache_data = malloc(bcache_nblks * bcache_blksize);
87 bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl));
88 bcache_miss = bit_alloc((bcache_nblks + 1) / 2);
89 if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) {
113 /* Flush the cache */
114 for (i = 0; i < bcache_nblks; i++) {
115 bcache_ctl[i].bc_count = -1;
116 bcache_ctl[i].bc_blkno = -1;
121 * Handle a transfer request; fill in parts of the request that can
122 * be satisfied by the cache, use the supplied strategy routine to do
123 * device I/O and then use the I/O results to populate the cache.
125 * Requests larger than 1/2 the cache size will be bypassed and go
126 * directly to the disk. XXX tune this.
129 bcache_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size,
130 char *buf, size_t *rsize)
132 static int bcache_unit = -1;
133 struct bcache_devdata *dd = (struct bcache_devdata *)devdata;
135 daddr_t p_blk, i, j, nblk;
140 if(bcache_unit != unit) {
145 /* bypass large requests, or when the cache is inactive */
146 if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) {
147 DEBUG("bypass %d from %d", size / bcache_blksize, blk);
149 return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize));
152 nblk = size / bcache_blksize;
155 /* Satisfy any cache hits up front */
156 for (i = 0; i < nblk; i++) {
157 if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) {
158 bit_set(bcache_miss, i); /* cache miss */
161 bit_clear(bcache_miss, i); /* cache hit */
166 /* Go back and fill in any misses XXX optimise */
170 for (i = 0; i < nblk; i++) {
171 if (bit_test(bcache_miss, i)) {
172 /* miss, add to pending transfer */
175 p_buf = buf + (bcache_blksize * i);
180 } else if (p_blk != -1) {
181 /* hit, complete pending transfer */
182 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
185 for (j = 0; j < p_size; j++)
186 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
191 /* pending transfer left */
192 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
195 for (j = 0; j < p_size; j++)
196 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
200 if ((result == 0) && (rsize != NULL))
207 * Insert a block into the cache. Retire the oldest block to do so, if required.
209 * XXX the LRU algorithm will fail after 2^31 blocks have been transferred.
212 bcache_insert(caddr_t buf, daddr_t blkno)
219 cand = 0; /* assume the first block */
220 ocount = bcache_ctl[0].bc_count;
222 /* find the oldest block */
223 for (i = 1; i < bcache_nblks; i++) {
224 if (bcache_ctl[i].bc_blkno == blkno) {
225 /* reuse old entry */
229 if (bcache_ctl[i].bc_count < ocount) {
230 ocount = bcache_ctl[i].bc_count;
235 DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount);
236 bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize);
237 bcache_ctl[cand].bc_blkno = blkno;
238 bcache_ctl[cand].bc_stamp = now;
239 bcache_ctl[cand].bc_count = bcache_bcount++;
243 * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old
244 * may be stale (removable media) and thus are discarded. Copy the block out
245 * if successful and return zero, or return nonzero on failure.
248 bcache_lookup(caddr_t buf, daddr_t blkno)
255 for (i = 0; i < bcache_nblks; i++)
257 if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) {
258 bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize);
259 DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp);
265 COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache);
268 command_bcache(int argc, char *argv[])
272 for (i = 0; i < bcache_nblks; i++) {
273 printf("%08x %04x %04x|", bcache_ctl[i].bc_blkno, (unsigned int)bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff);
274 if (((i + 1) % 4) == 0)
277 printf("\n%d ops %d bypasses %d hits %d misses %d flushes\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses, bcache_flushes);