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$");
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
53struct bcachectl
54{
55    daddr_t	bc_blkno;
56    time_t	bc_stamp;
57    int		bc_count;
58};
59
60static struct bcachectl	*bcache_ctl;
61static caddr_t		bcache_data;
62static bitstr_t		*bcache_miss;
63static u_int		bcache_nblks;
64static u_int		bcache_blksize;
65static u_int		bcache_hits, bcache_misses, bcache_ops, bcache_bypasses;
66static u_int		bcache_flushes;
67static u_int		bcache_bcount;
68
69static void	bcache_invalidate(daddr_t blkno);
70static void	bcache_insert(caddr_t buf, daddr_t blkno);
71static int	bcache_lookup(caddr_t buf, daddr_t blkno);
72
73/*
74 * Initialise the cache for (nblks) of (bsize).
75 */
76int
77bcache_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 */
109void
110bcache_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 */
127static int
128write_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 */
160static int
161read_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 */
226int
227bcache_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 */
262static void
263bcache_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 */
298static int
299bcache_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 */
319static void
320bcache_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
334COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache);
335
336static int
337command_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