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