Fully synchronize sys/boot from FreeBSD-5.x, but add / to the module path
[dragonfly.git] / sys / boot / common / bcache.c
CommitLineData
984263bc
MD
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 *
5ee58eed
MD
26 * $FreeBSD: src/sys/boot/common/bcache.c,v 1.12 2003/08/25 23:30:41 obrien Exp $
27 * $DragonFly: src/sys/boot/common/bcache.c,v 1.3 2003/11/10 06:08:31 dillon Exp $
984263bc
MD
28 */
29
30/*
31 * Simple LRU block cache
32 */
33
34#include <stand.h>
35#include <string.h>
36#include <bitstring.h>
37
38#include "bootstrap.h"
39
40/* #define BCACHE_DEBUG */
41
42#ifdef BCACHE_DEBUG
43#define BCACHE_TIMEOUT 10
5ee58eed 44# define DEBUG(fmt, args...) printf("%s: " fmt "\n" , __func__ , ## args)
984263bc
MD
45#else
46#define BCACHE_TIMEOUT 2
47# define DEBUG(fmt, args...)
48#endif
49
50
51struct bcachectl
52{
53 daddr_t bc_blkno;
54 time_t bc_stamp;
55 int bc_count;
56};
57
58static struct bcachectl *bcache_ctl;
59static caddr_t bcache_data;
60static bitstr_t *bcache_miss;
61static u_int bcache_nblks;
62static u_int bcache_blksize;
63static u_int bcache_hits, bcache_misses, bcache_ops, bcache_bypasses;
64static u_int bcache_flushes;
65static u_int bcache_bcount;
66
5ee58eed 67static void bcache_invalidate(daddr_t blkno);
984263bc
MD
68static void bcache_insert(caddr_t buf, daddr_t blkno);
69static int bcache_lookup(caddr_t buf, daddr_t blkno);
70
71/*
72 * Initialise the cache for (nblks) of (bsize).
73 */
74int
75bcache_init(u_int nblks, size_t bsize)
76{
77 /* discard any old contents */
78 if (bcache_data != NULL) {
79 free(bcache_data);
80 bcache_data = NULL;
81 free(bcache_ctl);
82 }
83
84 /* Allocate control structures */
85 bcache_nblks = nblks;
86 bcache_blksize = bsize;
87 bcache_data = malloc(bcache_nblks * bcache_blksize);
88 bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl));
89 bcache_miss = bit_alloc((bcache_nblks + 1) / 2);
90 if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) {
91 if (bcache_miss)
92 free(bcache_miss);
93 if (bcache_ctl)
94 free(bcache_ctl);
95 if (bcache_data)
96 free(bcache_data);
97 bcache_data = NULL;
98 return(ENOMEM);
99 }
100
101 return(0);
102}
103
104/*
105 * Flush the cache
106 */
107void
108bcache_flush(void)
109{
110 u_int i;
111
112 bcache_flushes++;
113
114 /* Flush the cache */
115 for (i = 0; i < bcache_nblks; i++) {
116 bcache_ctl[i].bc_count = -1;
117 bcache_ctl[i].bc_blkno = -1;
118 }
119}
120
5ee58eed
MD
121/*
122 * Handle a write request; write directly to the disk, and populate the
123 * cache with the new values.
984263bc 124 */
5ee58eed
MD
125static int
126write_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size,
984263bc
MD
127 char *buf, size_t *rsize)
128{
984263bc 129 struct bcache_devdata *dd = (struct bcache_devdata *)devdata;
5ee58eed
MD
130 daddr_t i, nblk;
131 int err;
984263bc 132
5ee58eed 133 nblk = size / bcache_blksize;
984263bc 134
5ee58eed
MD
135 /* Invalidate the blocks being written */
136 for (i = 0; i < nblk; i++) {
137 bcache_invalidate(blk + i);
984263bc
MD
138 }
139
5ee58eed
MD
140 /* Write the blocks */
141 err = dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize);
142
143 /* Populate the block cache with the new data */
144 if (err == 0) {
145 for (i = 0; i < nblk; i++) {
146 bcache_insert(buf + (i * bcache_blksize),blk + i);
147 }
984263bc
MD
148 }
149
5ee58eed
MD
150 return err;
151}
152
153/*
154 * Handle a read request; fill in parts of the request that can
155 * be satisfied by the cache, use the supplied strategy routine to do
156 * device I/O and then use the I/O results to populate the cache.
157 */
158static int
159read_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size,
160 char *buf, size_t *rsize)
161{
162 struct bcache_devdata *dd = (struct bcache_devdata *)devdata;
163 int p_size, result;
164 daddr_t p_blk, i, j, nblk;
165 caddr_t p_buf;
166
984263bc
MD
167 nblk = size / bcache_blksize;
168 result = 0;
169
170 /* Satisfy any cache hits up front */
171 for (i = 0; i < nblk; i++) {
172 if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) {
173 bit_set(bcache_miss, i); /* cache miss */
174 bcache_misses++;
175 } else {
176 bit_clear(bcache_miss, i); /* cache hit */
177 bcache_hits++;
178 }
179 }
180
181 /* Go back and fill in any misses XXX optimise */
182 p_blk = -1;
183 p_buf = NULL;
184 p_size = 0;
185 for (i = 0; i < nblk; i++) {
186 if (bit_test(bcache_miss, i)) {
187 /* miss, add to pending transfer */
188 if (p_blk == -1) {
189 p_blk = blk + i;
190 p_buf = buf + (bcache_blksize * i);
191 p_size = 1;
192 } else {
193 p_size++;
194 }
195 } else if (p_blk != -1) {
196 /* hit, complete pending transfer */
197 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
198 if (result != 0)
199 goto done;
200 for (j = 0; j < p_size; j++)
201 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
202 p_blk = -1;
203 }
204 }
205 if (p_blk != -1) {
206 /* pending transfer left */
207 result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
208 if (result != 0)
209 goto done;
210 for (j = 0; j < p_size; j++)
211 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
212 }
213
214 done:
215 if ((result == 0) && (rsize != NULL))
216 *rsize = size;
217 return(result);
218}
219
5ee58eed
MD
220/*
221 * Requests larger than 1/2 the cache size will be bypassed and go
222 * directly to the disk. XXX tune this.
223 */
224int
225bcache_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size,
226 char *buf, size_t *rsize)
227{
228 static int bcache_unit = -1;
229 struct bcache_devdata *dd = (struct bcache_devdata *)devdata;
230
231 bcache_ops++;
232
233 if(bcache_unit != unit) {
234 bcache_flush();
235 bcache_unit = unit;
236 }
237
238 /* bypass large requests, or when the cache is inactive */
239 if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) {
240 DEBUG("bypass %d from %d", size / bcache_blksize, blk);
241 bcache_bypasses++;
242 return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize));
243 }
244
245 switch (rw) {
246 case F_READ:
247 return read_strategy(devdata, unit, rw, blk, size, buf, rsize);
248 case F_WRITE:
249 return write_strategy(devdata, unit, rw, blk, size, buf, rsize);
250 }
251 return -1;
252}
253
984263bc
MD
254
255/*
256 * Insert a block into the cache. Retire the oldest block to do so, if required.
257 *
258 * XXX the LRU algorithm will fail after 2^31 blocks have been transferred.
259 */
260static void
261bcache_insert(caddr_t buf, daddr_t blkno)
262{
263 time_t now;
264 int cand, ocount;
265 u_int i;
266
267 time(&now);
268 cand = 0; /* assume the first block */
269 ocount = bcache_ctl[0].bc_count;
270
271 /* find the oldest block */
272 for (i = 1; i < bcache_nblks; i++) {
273 if (bcache_ctl[i].bc_blkno == blkno) {
274 /* reuse old entry */
275 cand = i;
276 break;
277 }
278 if (bcache_ctl[i].bc_count < ocount) {
279 ocount = bcache_ctl[i].bc_count;
280 cand = i;
281 }
282 }
283
284 DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount);
285 bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize);
286 bcache_ctl[cand].bc_blkno = blkno;
287 bcache_ctl[cand].bc_stamp = now;
288 bcache_ctl[cand].bc_count = bcache_bcount++;
289}
290
291/*
292 * Look for a block in the cache. Blocks more than BCACHE_TIMEOUT seconds old
293 * may be stale (removable media) and thus are discarded. Copy the block out
294 * if successful and return zero, or return nonzero on failure.
295 */
296static int
297bcache_lookup(caddr_t buf, daddr_t blkno)
298{
299 time_t now;
300 u_int i;
301
302 time(&now);
303
304 for (i = 0; i < bcache_nblks; i++)
305 /* cache hit? */
306 if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) {
307 bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize);
308 DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp);
309 return(0);
310 }
311 return(ENOENT);
312}
313
5ee58eed
MD
314/*
315 * Invalidate a block from the cache.
316 */
317static void
318bcache_invalidate(daddr_t blkno)
319{
320 u_int i;
321
322 for (i = 0; i < bcache_nblks; i++) {
323 if (bcache_ctl[i].bc_blkno == blkno) {
324 bcache_ctl[i].bc_count = -1;
325 bcache_ctl[i].bc_blkno = -1;
326 DEBUG("invalidate blk %d", blkno);
327 break;
328 }
329 }
330}
331
984263bc
MD
332COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache);
333
334static int
335command_bcache(int argc, char *argv[])
336{
337 u_int i;
338
339 for (i = 0; i < bcache_nblks; i++) {
340 printf("%08x %04x %04x|", bcache_ctl[i].bc_blkno, (unsigned int)bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff);
341 if (((i + 1) % 4) == 0)
342 printf("\n");
343 }
344 printf("\n%d ops %d bypasses %d hits %d misses %d flushes\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses, bcache_flushes);
345 return(CMD_OK);
346}
347