bcache.c revision 40834
1/*
2 * mjs copyright
3 */
4
5/*
6 * Simple LRU block cache
7 */
8
9#include <stand.h>
10#include <string.h>
11#include <bitstring.h>
12
13#include "bootstrap.h"
14
15/* #define BCACHE_DEBUG */
16
17#ifdef BCACHE_DEBUG
18#define BCACHE_TIMEOUT	10
19# define DEBUG(fmt, args...)	printf("%s: " fmt "\n" , __FUNCTION__ , ## args)
20#else
21#define BCACHE_TIMEOUT	2
22# define DEBUG(fmt, args...)
23#endif
24
25
26struct bcachectl
27{
28    daddr_t	bc_blkno;
29    time_t	bc_stamp;
30};
31
32static struct bcachectl	*bcache_ctl;
33static caddr_t		bcache_data;
34static bitstr_t		*bcache_miss;
35static int		bcache_nblks;
36static int		bcache_blksize;
37static int		bcache_hits, bcache_misses, bcache_ops, bcache_bypasses;
38
39static void	bcache_insert(caddr_t buf, daddr_t blkno);
40static int	bcache_lookup(caddr_t buf, daddr_t blkno);
41
42/*
43 * Initialise the cache for (nblks) of (bsize).
44 */
45int
46bcache_init(int nblks, size_t bsize)
47{
48    int		i;
49
50    /* discard any old contents */
51    if (bcache_data != NULL) {
52	free(bcache_data);
53	bcache_data = NULL;
54	free(bcache_ctl);
55    }
56
57    /* Allocate control structures */
58    bcache_nblks = nblks;
59    bcache_blksize = bsize;
60    bcache_data = malloc(bcache_nblks * bcache_blksize);
61    bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl));
62    bcache_miss = bit_alloc((bcache_nblks + 1) / 2);
63    if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) {
64	if (bcache_miss)
65	    free(bcache_miss);
66	if (bcache_ctl)
67	    free(bcache_ctl);
68	if (bcache_data)
69	    free(bcache_data);
70	bcache_data = NULL;
71	return(ENOMEM);
72    }
73
74    /* Invalidate the cache */
75    for (i = 0; i < bcache_nblks; i++)
76	bcache_ctl[i].bc_stamp = 0;
77
78    return(0);
79}
80
81/*
82 * Handle a transfer request; fill in parts of the request that can
83 * be satisfied by the cache, use the supplied strategy routine to do
84 * device I/O and then use the I/O results to populate the cache.
85 *
86 * Requests larger than 1/2 the cache size will be bypassed and go
87 * directly to the disk.  XXX tune this.
88 */
89int
90bcache_strategy(void *devdata, int rw, daddr_t blk, size_t size, void *buf, size_t *rsize)
91{
92    struct bcache_devdata	*dd = (struct bcache_devdata *)devdata;
93    int				nblk, p_size;
94    daddr_t			p_blk;
95    caddr_t			p_buf;
96    int				i, j, result;
97
98    bcache_ops++;
99
100    /* bypass large requests, or when the cache is inactive */
101    if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) {
102	DEBUG("bypass %d from %d", size / bcache_blksize, blk);
103	bcache_bypasses++;
104	return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize));
105    }
106
107    nblk = size / bcache_blksize;
108    result = 0;
109
110    /* Satisfy any cache hits up front */
111    for (i = 0; i < nblk; i++) {
112	if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) {
113	    bit_set(bcache_miss, i);	/* cache miss */
114	    bcache_misses++;
115	} else {
116	    bit_clear(bcache_miss, i);	/* cache hit */
117	    bcache_hits++;
118	}
119    }
120
121    /* Go back and fill in any misses  XXX optimise */
122    p_blk = -1;
123    p_buf = NULL;
124    p_size = 0;
125    for (i = 0; i < nblk; i++) {
126	if (bit_test(bcache_miss, i)) {
127	    /* miss, add to pending transfer */
128	    if (p_blk == -1) {
129		p_blk = blk + i;
130		p_buf = buf + (bcache_blksize * i);
131		p_size = 1;
132	    } else {
133		p_size++;
134	    }
135	} else if (p_blk != -1) {
136	    /* hit, complete pending transfer */
137	    result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
138	    if (result != 0)
139		goto done;
140	    for (j = 0; j < p_size; j++)
141		bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
142	    p_blk = -1;
143	}
144    }
145    if (p_blk != -1) {
146	/* pending transfer left */
147	result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
148	if (result != 0)
149	    goto done;
150	for (j = 0; j < p_size; j++)
151	    bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
152    }
153
154 done:
155    if ((result == 0) && (rsize != NULL))
156	*rsize = size;
157    return(result);
158}
159
160
161/*
162 * Insert a block into the cache.  Retire the oldest block to do so, if required.
163 */
164static void
165bcache_insert(caddr_t buf, daddr_t blkno)
166{
167    time_t	now;
168    int		i, cand;
169
170    time(&now);
171
172    /* find the oldest block */
173    for (cand = 0, i = 1; i < bcache_nblks; i++) {
174	if (bcache_ctl[i].bc_blkno == blkno) {
175	    /* reuse old entry */
176	    cand = i;
177	    break;
178	}
179	if (bcache_ctl[i].bc_stamp < now)
180	    cand = i;
181    }
182
183    DEBUG("insert blk %d -> %d @ %d", blkno, cand, now);
184    bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize);
185    bcache_ctl[cand].bc_blkno = blkno;
186    bcache_ctl[cand].bc_stamp = now;
187}
188
189/*
190 * Look for a block in the cache.  Blocks more than BCACHE_TIMEOUT seconds old
191 *  may be stale (removable media) and thus are discarded.  Copy the block out
192 * if successful and return zero, or return nonzero on failure.
193 */
194static int
195bcache_lookup(caddr_t buf, daddr_t blkno)
196{
197    time_t	now;
198    int		i;
199
200    time(&now);
201
202    for (i = 0; i < bcache_nblks; i++)
203	/* cache hit? */
204	if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) {
205	    bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize);
206	    DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp);
207	    return(0);
208	}
209    return(ENOENT);
210}
211
212COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache);
213
214static int
215command_bcache(int argc, char *argv[])
216{
217    int		i;
218
219    for (i = 0; i < bcache_nblks; i++) {
220	printf("  %02x: %08x %04x", i, bcache_ctl[i].bc_blkno, bcache_ctl[i].bc_stamp & 0xffff);
221	if (((i + 1) % 4) == 0)
222	    printf("\n");
223    }
224    printf("\n%d ops  %d bypasses  %d hits  %d misses\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses);
225    return(CMD_OK);
226}
227
228