bufcache.c revision 1.2 1 1.2 perseant /* $NetBSD: bufcache.c,v 1.2 2003/03/31 19:56:59 perseant Exp $ */
2 1.1 perseant /*-
3 1.1 perseant * Copyright (c) 2003 The NetBSD Foundation, Inc.
4 1.1 perseant * All rights reserved.
5 1.1 perseant *
6 1.1 perseant * This code is derived from software contributed to The NetBSD Foundation
7 1.1 perseant * by Konrad E. Schroder <perseant (at) hhhh.org>.
8 1.1 perseant *
9 1.1 perseant * Redistribution and use in source and binary forms, with or without
10 1.1 perseant * modification, are permitted provided that the following conditions
11 1.1 perseant * are met:
12 1.1 perseant * 1. Redistributions of source code must retain the above copyright
13 1.1 perseant * notice, this list of conditions and the following disclaimer.
14 1.1 perseant * 2. Redistributions in binary form must reproduce the above copyright
15 1.1 perseant * notice, this list of conditions and the following disclaimer in the
16 1.1 perseant * documentation and/or other materials provided with the distribution.
17 1.1 perseant * 3. All advertising materials mentioning features or use of this software
18 1.1 perseant * must display the following acknowledgement:
19 1.1 perseant * This product includes software developed by the NetBSD
20 1.1 perseant * Foundation, Inc. and its contributors.
21 1.1 perseant * 4. Neither the name of The NetBSD Foundation nor the names of its
22 1.1 perseant * contributors may be used to endorse or promote products derived
23 1.1 perseant * from this software without specific prior written permission.
24 1.1 perseant *
25 1.1 perseant * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
26 1.1 perseant * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
27 1.1 perseant * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 1.1 perseant * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
29 1.1 perseant * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 1.1 perseant * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 1.1 perseant * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 1.1 perseant * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 1.1 perseant * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 1.1 perseant * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 1.1 perseant * POSSIBILITY OF SUCH DAMAGE.
36 1.1 perseant */
37 1.1 perseant
38 1.1 perseant #include <sys/types.h>
39 1.1 perseant #include <sys/param.h>
40 1.1 perseant #include <sys/time.h>
41 1.1 perseant #include <sys/buf.h>
42 1.1 perseant #include <sys/queue.h>
43 1.1 perseant #include <sys/mount.h>
44 1.1 perseant
45 1.1 perseant #include <assert.h>
46 1.1 perseant #include <err.h>
47 1.1 perseant #include <stdio.h>
48 1.1 perseant #include <stdlib.h>
49 1.1 perseant #include <string.h>
50 1.1 perseant #include <unistd.h>
51 1.1 perseant
52 1.1 perseant #include "bufcache.h"
53 1.1 perseant #include "vnode.h"
54 1.1 perseant
55 1.1 perseant /*
56 1.1 perseant * Definitions for the buffer free lists.
57 1.1 perseant */
58 1.1 perseant #define BQUEUES 3 /* number of free buffer queues */
59 1.1 perseant
60 1.1 perseant #define BQ_LOCKED 0 /* super-blocks &c */
61 1.1 perseant #define BQ_LRU 1 /* lru, useful buffers */
62 1.1 perseant #define BQ_AGE 2 /* rubbish */
63 1.1 perseant
64 1.1 perseant TAILQ_HEAD(bqueues, ubuf) bufqueues[BQUEUES];
65 1.1 perseant
66 1.1 perseant #define HASH_MAX 101
67 1.1 perseant
68 1.1 perseant struct bufhash_struct bufhash[HASH_MAX];
69 1.1 perseant
70 1.1 perseant int maxbufs = BUF_CACHE_SIZE;
71 1.1 perseant int nbufs = 0;
72 1.1 perseant int cachehits = 0;
73 1.1 perseant int cachemisses = 0;
74 1.1 perseant int hashmax = 0;
75 1.1 perseant off_t locked_queue_bytes = 0;
76 1.1 perseant
77 1.1 perseant /* Simple buffer hash function */
78 1.1 perseant static int
79 1.1 perseant vl_hash(struct uvnode * vp, daddr_t lbn)
80 1.1 perseant {
81 1.1 perseant return (int)((unsigned long) vp + lbn) % HASH_MAX;
82 1.1 perseant }
83 1.1 perseant
84 1.1 perseant /* Initialize buffer cache */
85 1.1 perseant void
86 1.1 perseant bufinit(void)
87 1.1 perseant {
88 1.1 perseant int i;
89 1.1 perseant
90 1.1 perseant for (i = 0; i < BQUEUES; i++) {
91 1.1 perseant TAILQ_INIT(&bufqueues[i]);
92 1.1 perseant }
93 1.1 perseant for (i = 0; i < HASH_MAX; i++)
94 1.1 perseant LIST_INIT(&bufhash[HASH_MAX]);
95 1.1 perseant }
96 1.1 perseant
97 1.1 perseant /* Print statistics of buffer cache usage */
98 1.1 perseant void
99 1.1 perseant bufstats(void)
100 1.1 perseant {
101 1.1 perseant printf("buffer cache: %d hits %d misses (%2.2f%%); hash depth %d\n",
102 1.1 perseant cachehits, cachemisses,
103 1.1 perseant (cachehits * 100.0) / (cachehits + cachemisses),
104 1.1 perseant hashmax);
105 1.1 perseant }
106 1.1 perseant
107 1.1 perseant /*
108 1.1 perseant * Remove a buffer from the cache.
109 1.1 perseant * Caller must remove the buffer from its free list.
110 1.1 perseant */
111 1.1 perseant void
112 1.1 perseant buf_destroy(struct ubuf * bp)
113 1.1 perseant {
114 1.1 perseant bp->b_flags |= B_NEEDCOMMIT;
115 1.1 perseant LIST_REMOVE(bp, b_vnbufs);
116 1.1 perseant LIST_REMOVE(bp, b_hash);
117 1.1 perseant free(bp->b_data);
118 1.1 perseant free(bp);
119 1.1 perseant --nbufs;
120 1.1 perseant }
121 1.1 perseant
122 1.1 perseant /* Remove a buffer from its free list. */
123 1.1 perseant void
124 1.1 perseant bremfree(struct ubuf * bp)
125 1.1 perseant {
126 1.1 perseant struct bqueues *dp = NULL;
127 1.1 perseant
128 1.1 perseant /*
129 1.1 perseant * We only calculate the head of the freelist when removing
130 1.1 perseant * the last element of the list as that is the only time that
131 1.1 perseant * it is needed (e.g. to reset the tail pointer).
132 1.1 perseant *
133 1.1 perseant * NB: This makes an assumption about how tailq's are implemented.
134 1.1 perseant */
135 1.2 perseant if (bp->b_flags & B_LOCKED) {
136 1.1 perseant locked_queue_bytes -= bp->b_bcount;
137 1.2 perseant }
138 1.1 perseant if (TAILQ_NEXT(bp, b_freelist) == NULL) {
139 1.1 perseant for (dp = bufqueues; dp < &bufqueues[BQUEUES]; dp++)
140 1.1 perseant if (dp->tqh_last == &bp->b_freelist.tqe_next)
141 1.1 perseant break;
142 1.1 perseant if (dp == &bufqueues[BQUEUES])
143 1.1 perseant errx(1, "bremfree: lost tail");
144 1.1 perseant }
145 1.1 perseant ++bp->b_vp->v_usecount;
146 1.1 perseant TAILQ_REMOVE(dp, bp, b_freelist);
147 1.1 perseant }
148 1.1 perseant
149 1.1 perseant /* Return a buffer if it is in the cache, otherwise return NULL. */
150 1.1 perseant struct ubuf *
151 1.1 perseant incore(struct uvnode * vp, int lbn)
152 1.1 perseant {
153 1.1 perseant struct ubuf *bp;
154 1.1 perseant int hash, depth;
155 1.1 perseant
156 1.1 perseant hash = vl_hash(vp, lbn);
157 1.1 perseant /* XXX use a real hash instead. */
158 1.1 perseant depth = 0;
159 1.1 perseant LIST_FOREACH(bp, &bufhash[hash], b_hash) {
160 1.1 perseant if (++depth > hashmax)
161 1.1 perseant hashmax = depth;
162 1.1 perseant if (bp->b_vp == vp && bp->b_lblkno == lbn) {
163 1.1 perseant return bp;
164 1.1 perseant }
165 1.1 perseant }
166 1.1 perseant return NULL;
167 1.1 perseant }
168 1.1 perseant
169 1.1 perseant /*
170 1.1 perseant * Return a buffer of the given size, lbn and uvnode.
171 1.1 perseant * If none is in core, make a new one.
172 1.1 perseant */
173 1.1 perseant struct ubuf *
174 1.1 perseant getblk(struct uvnode * vp, daddr_t lbn, int size)
175 1.1 perseant {
176 1.1 perseant struct ubuf *bp;
177 1.1 perseant
178 1.1 perseant /*
179 1.1 perseant * First check the buffer cache lists.
180 1.1 perseant */
181 1.1 perseant if ((bp = incore(vp, lbn)) != NULL) {
182 1.1 perseant assert(!(bp->b_flags & B_NEEDCOMMIT));
183 1.1 perseant assert(!(bp->b_flags & B_BUSY));
184 1.1 perseant assert(bp->b_bcount == size);
185 1.1 perseant bp->b_flags |= B_BUSY;
186 1.1 perseant bremfree(bp);
187 1.1 perseant return bp;
188 1.1 perseant }
189 1.1 perseant /*
190 1.1 perseant * Not on the list.
191 1.1 perseant * Get a new block of the appropriate size and use that.
192 1.1 perseant * If not enough space, free blocks from the AGE and LRU lists
193 1.1 perseant * to make room.
194 1.1 perseant */
195 1.1 perseant while (nbufs >= maxbufs) {
196 1.1 perseant bp = TAILQ_FIRST(&bufqueues[BQ_AGE]);
197 1.1 perseant if (bp)
198 1.1 perseant TAILQ_REMOVE(&bufqueues[BQ_AGE], bp, b_freelist);
199 1.1 perseant if (bp == NULL) {
200 1.1 perseant bp = TAILQ_FIRST(&bufqueues[BQ_LRU]);
201 1.1 perseant if (bp)
202 1.1 perseant TAILQ_REMOVE(&bufqueues[BQ_AGE], bp,
203 1.1 perseant b_freelist);
204 1.1 perseant }
205 1.1 perseant if (bp) {
206 1.1 perseant if (bp->b_flags & B_DELWRI)
207 1.1 perseant VOP_STRATEGY(bp);
208 1.1 perseant buf_destroy(bp);
209 1.1 perseant }
210 1.1 perseant #ifdef DEBUG
211 1.1 perseant else {
212 1.1 perseant warnx("no free buffers, allocating more than %d",
213 1.1 perseant maxbufs);
214 1.1 perseant }
215 1.1 perseant #endif
216 1.1 perseant }
217 1.1 perseant ++nbufs;
218 1.1 perseant bp = (struct ubuf *) malloc(sizeof(*bp));
219 1.1 perseant memset(bp, 0, sizeof(*bp));
220 1.1 perseant bp->b_data = malloc(size);
221 1.1 perseant memset(bp->b_data, 0, size);
222 1.1 perseant
223 1.1 perseant bp->b_vp = vp;
224 1.1 perseant bp->b_blkno = bp->b_lblkno = lbn;
225 1.1 perseant bp->b_bcount = size;
226 1.1 perseant LIST_INSERT_HEAD(&bufhash[vl_hash(vp, lbn)], bp, b_hash);
227 1.1 perseant LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
228 1.1 perseant bp->b_flags = B_BUSY;
229 1.1 perseant
230 1.1 perseant return bp;
231 1.1 perseant }
232 1.1 perseant
233 1.1 perseant /* Write a buffer to disk according to its strategy routine. */
234 1.1 perseant void
235 1.1 perseant bwrite(struct ubuf * bp)
236 1.1 perseant {
237 1.1 perseant bp->b_flags &= ~(B_READ | B_DONE | B_DELWRI | B_LOCKED);
238 1.1 perseant VOP_STRATEGY(bp);
239 1.1 perseant bp->b_flags |= B_DONE;
240 1.1 perseant reassignbuf(bp, bp->b_vp);
241 1.1 perseant brelse(bp);
242 1.1 perseant }
243 1.1 perseant
244 1.1 perseant /* Put a buffer back on its free list, clear B_BUSY. */
245 1.1 perseant void
246 1.1 perseant brelse(struct ubuf * bp)
247 1.1 perseant {
248 1.1 perseant int age;
249 1.1 perseant
250 1.1 perseant assert(!(bp->b_flags & B_NEEDCOMMIT));
251 1.1 perseant assert(bp->b_flags & B_BUSY);
252 1.1 perseant
253 1.1 perseant age = bp->b_flags & B_AGE;
254 1.1 perseant bp->b_flags &= ~(B_BUSY | B_AGE);
255 1.1 perseant if (bp->b_flags & B_INVAL) {
256 1.1 perseant buf_destroy(bp);
257 1.1 perseant return;
258 1.1 perseant }
259 1.1 perseant if (bp->b_flags & B_LOCKED) {
260 1.1 perseant locked_queue_bytes += bp->b_bcount;
261 1.1 perseant TAILQ_INSERT_TAIL(&bufqueues[BQ_LOCKED], bp, b_freelist);
262 1.1 perseant } else if (age) {
263 1.1 perseant TAILQ_INSERT_TAIL(&bufqueues[BQ_AGE], bp, b_freelist);
264 1.1 perseant } else {
265 1.1 perseant TAILQ_INSERT_TAIL(&bufqueues[BQ_LRU], bp, b_freelist);
266 1.1 perseant }
267 1.1 perseant --bp->b_vp->v_usecount;
268 1.1 perseant }
269 1.1 perseant
270 1.1 perseant /* Read the given block from disk, return it B_BUSY. */
271 1.1 perseant int
272 1.1 perseant bread(struct uvnode * vp, daddr_t lbn, int size, struct ucred * unused,
273 1.1 perseant struct ubuf ** bpp)
274 1.1 perseant {
275 1.1 perseant struct ubuf *bp;
276 1.1 perseant daddr_t daddr;
277 1.1 perseant int error, count;
278 1.1 perseant
279 1.1 perseant bp = getblk(vp, lbn, size);
280 1.1 perseant *bpp = bp;
281 1.1 perseant if (bp->b_flags & (B_DELWRI | B_DONE)) {
282 1.1 perseant ++cachehits;
283 1.1 perseant return 0;
284 1.1 perseant }
285 1.1 perseant ++cachemisses;
286 1.1 perseant
287 1.1 perseant /*
288 1.1 perseant * Not found. Need to find that block's location on disk,
289 1.1 perseant * and load it in.
290 1.1 perseant */
291 1.1 perseant daddr = -1;
292 1.1 perseant error = VOP_BMAP(vp, lbn, &daddr);
293 1.1 perseant bp->b_blkno = daddr;
294 1.1 perseant if (daddr >= 0) {
295 1.1 perseant count = pread(vp->v_fd, bp->b_data, bp->b_bcount,
296 1.1 perseant dbtob((off_t) daddr));
297 1.1 perseant if (count == bp->b_bcount) {
298 1.1 perseant bp->b_flags |= B_DONE;
299 1.1 perseant return 0;
300 1.1 perseant }
301 1.1 perseant return -1;
302 1.1 perseant }
303 1.1 perseant memset(bp->b_data, 0, bp->b_bcount);
304 1.1 perseant return 0;
305 1.1 perseant }
306 1.1 perseant
307 1.1 perseant /* Move a buffer between dirty and clean block lists. */
308 1.1 perseant void
309 1.1 perseant reassignbuf(struct ubuf * bp, struct uvnode * vp)
310 1.1 perseant {
311 1.1 perseant LIST_REMOVE(bp, b_vnbufs);
312 1.1 perseant if (bp->b_flags & B_DELWRI) {
313 1.1 perseant LIST_INSERT_HEAD(&vp->v_dirtyblkhd, bp, b_vnbufs);
314 1.1 perseant } else {
315 1.1 perseant LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
316 1.1 perseant }
317 1.1 perseant }
318