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